Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <algorithm>
- #include <vector>
- #include <array>
- using namespace std;
- ifstream cin("trumplandia.in");
- ofstream cout("trumplandia.out");
- typedef long long ll;
- const int mxN = 2e5;
- vector<array<int,4>> edges, sorted;
- vector<array<int,2>> adj[mxN+10];
- ll used[mxN+10], sol[mxN+10],p[20][mxN+10], par[mxN+10],sizes[mxN+10];
- ll maxEdge[20][mxN+10], totalCost, depth[mxN+10];
- bool visited[mxN+10];
- void DFS(int node)
- {
- visited[node] = true;
- for(auto it : adj[node])
- if(!visited[it[0]])
- {
- depth[it[0]] = depth[node] + 1;
- p[0][it[0]] = node;
- maxEdge[0][it[0]] = it[1];
- visited[it[0]] = true;
- DFS(it[0]);
- }
- }
- int get(int a)
- {
- if(a != par[a])
- par[a] = get(par[a]);
- return par[a];
- }
- void unite(int a, int b)
- {
- a = get(a);
- b = get(b);
- if(a == b) return;
- if(sizes[a] < sizes[b]) swap(a,b);
- par[b] = a;
- sizes[a] += sizes[b];
- }
- int up(int a, int k)
- {
- for(int bit = 0;bit<=18;bit++)
- if((1<<bit) & k)
- a = p[bit][a];
- return a;
- }
- ll upMax(int a, int k)
- {
- ll sol = 0;
- for(int bit = 0;bit<=18;bit++)
- if((1<<bit) & k)
- sol = max(sol,maxEdge[bit][a]), a = p[bit][a];
- return sol;
- }
- int LCA(int a, int b)
- {
- if(depth[a] < depth[b]) swap(a,b);
- if(depth[a] != depth[b]) a = up(a,depth[a] - depth[b]);
- for(int bit = 18;bit>=0 && a != b;bit--)
- {
- int aux1 = up(a, (1<<bit) - 1);
- int aux2 = up(b, (1<<bit) - 1);
- if(aux1 != aux2)
- a = p[0][aux1], b = p[0][aux2];
- }
- return a;
- }
- int main()
- {
- int n , m , q;
- cin >> n >> m >> q;
- for(int i = 1;i<=n;i++)
- par[i] = i, sizes[i] = 1;
- for(int i = 1;i<=m;i++)
- {
- int a, b, w;
- cin >> a >> b >> w;
- edges.push_back({w,a,b,i});
- }
- sorted = edges;
- sort(sorted.begin(),sorted.end());
- for(auto it : sorted)
- {
- if(get(it[1]) != get(it[2]))
- {
- unite(it[1],it[2]);
- totalCost += it[0];
- adj[it[1]].push_back({it[2],it[0]});
- adj[it[2]].push_back({it[1],it[0]});
- used[it[3]] = true;
- }
- }
- depth[1] = 1;
- DFS(1);
- for(int i = 1;i<=18;i++)
- for(int j = 1;j<=n;j++)
- {
- p[i][j] = p[i-1][p[i-1][j]];
- maxEdge[i][j] = max(maxEdge[i-1][j], maxEdge[i-1][p[i-1][j]]);
- }
- cout << totalCost << '\n';
- for(int i = 0;i<m;i++)
- {
- if(used[i+1]) sol[i+1] = totalCost;
- else
- {
- int a = edges[i][1], b = edges[i][2];
- int lca = LCA(a,b);
- int removed = max(upMax(a,depth[a] - depth[lca]), upMax(b,depth[b] - depth[lca]));
- sol[i+1] = totalCost - removed + edges[i][0];
- }
- }
- for(int i = 1;i<=q;i++)
- {
- int query; cin >> query;
- cout << sol[query] << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
