Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ```
- ll n, k;
- cin>>n>>k;
- unordered_map<ll ,ll>Important;
- for(int i=0;i<k;i++){
- ll x;
- cin>>x;
- x--;
- Important[x] = 1;
- }
- vector<pair<ll, ll>>adj[n];
- vector<tuple<ll, ll, ll>>Edges;
- vector<ll>deg(n, 0);
- for(int i=0;i<n-1;i++){
- ll u, v, w;
- cin>>u>>v>>w;
- u--;
- v--;
- adj[u].pb({v ,w});
- adj[v].pb({u ,w});
- Edges.pb({u ,v ,w});
- deg[u]++;
- deg[v]++;
- }
- //to truncate the tree
- unordered_map<ll ,ll>Deleted_Nodes;
- queue<ll>q;
- for(int i=0;i<n;i++){
- if(deg[i]==1 && !Important.count(i)){
- q.push(i);
- }
- }
- while(!q.empty()){
- ll node = q.front();
- q.pop();
- Deleted_Nodes[node] = 1;
- for(auto it : adj[node]){
- deg[it.first]--;
- if(deg[it.first]==1 && !Important.count(it.first)){
- q.push(it.first);
- }
- }
- }
- //remake the tree excluding deleted edges
- vector<pair<ll, ll>>new_Adj[n];
- ll total =0;
- ll start_node;
- for(auto it : Edges){
- ll u = get<0>(it);
- ll v = get<1>(it);
- ll w = get<2>(it);
- if(Deleted_Nodes.count(u) || Deleted_Nodes.count(v)) continue;
- start_node=u; //to start dfs
- new_Adj[u].pb({v ,w});
- new_Adj[v].pb({u ,w});
- total += 2*w;
- }
- //Now we have to find the diameter
- //find the node at the gretest depth,
- // again run the dfs for deppest node from this
- vector<ll>depth(n, 0);
- ll max_node;
- ll max_depth = -INF;
- function<void(ll, ll)> dfs2=[&](ll root , ll parent){
- for(auto it : new_Adj[root]){
- if(it.first==parent) continue;
- depth[it.first] = depth[root] + it.second;
- dfs2(it.first , root);
- }
- if(max_depth < depth[root]){
- max_depth = depth[root];
- max_node = root;
- }
- };
- //send the node a connected graph
- dfs2(start_node, -1);
- depth.assign(n, 0);
- max_depth = -INF;
- function<void(ll, ll)> dfs3=[&](ll root , ll parent){
- for(auto it : new_Adj[root]){
- if(it.first==parent) continue;
- depth[it.first] = depth[root] + it.second;
- dfs3(it.first , root);
- }
- max_depth = max(max_depth , depth[root]);
- };
- dfs3(max_node , -1);
- cout<<total - max_depth<<endl;
- ```
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement