Advertisement
Guest User

Untitled

a guest
Jul 15th, 2023
226
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.47 KB | None | 0 0
  1. ```
  2.     ll n, k;
  3.     cin>>n>>k;
  4.     unordered_map<ll ,ll>Important;
  5.     for(int i=0;i<k;i++){
  6.         ll x;
  7.         cin>>x;
  8.         x--;
  9.         Important[x] = 1;
  10.     }
  11.  
  12.     vector<pair<ll, ll>>adj[n];
  13.     vector<tuple<ll, ll, ll>>Edges;
  14.     vector<ll>deg(n, 0);
  15.     for(int i=0;i<n-1;i++){
  16.         ll u, v, w;
  17.         cin>>u>>v>>w;
  18.         u--;
  19.         v--;
  20.         adj[u].pb({v ,w});
  21.         adj[v].pb({u ,w});
  22.         Edges.pb({u ,v ,w});
  23.         deg[u]++;
  24.         deg[v]++;
  25.     }
  26.  
  27.     //to truncate the tree
  28.     unordered_map<ll ,ll>Deleted_Nodes;
  29.     queue<ll>q;
  30.     for(int i=0;i<n;i++){
  31.         if(deg[i]==1 && !Important.count(i)){
  32.             q.push(i);
  33.         }
  34.     }
  35.     while(!q.empty()){
  36.         ll node = q.front();
  37.         q.pop();
  38.         Deleted_Nodes[node] = 1;
  39.         for(auto it : adj[node]){
  40.             deg[it.first]--;
  41.             if(deg[it.first]==1 && !Important.count(it.first)){
  42.                 q.push(it.first);
  43.             }
  44.         }
  45.     }
  46.  
  47.     //remake the tree excluding deleted edges
  48.     vector<pair<ll, ll>>new_Adj[n];
  49.     ll total =0;
  50.     ll start_node;
  51.     for(auto it : Edges){
  52.         ll u = get<0>(it);
  53.         ll v = get<1>(it);
  54.         ll w = get<2>(it);
  55.         if(Deleted_Nodes.count(u) || Deleted_Nodes.count(v)) continue;
  56.         start_node=u;  //to start dfs
  57.         new_Adj[u].pb({v ,w});
  58.         new_Adj[v].pb({u ,w});
  59.         total += 2*w;
  60.     }
  61.  
  62.     //Now we have to find the diameter
  63.     //find the node at the gretest depth,
  64.     // again run the dfs for deppest node from this
  65.     vector<ll>depth(n, 0);
  66.     ll max_node;
  67.     ll max_depth = -INF;
  68.     function<void(ll, ll)> dfs2=[&](ll root , ll parent){
  69.         for(auto it : new_Adj[root]){
  70.             if(it.first==parent) continue;
  71.             depth[it.first] = depth[root] + it.second;
  72.             dfs2(it.first , root);
  73.         }
  74.  
  75.         if(max_depth < depth[root]){
  76.             max_depth = depth[root];
  77.             max_node = root;
  78.         }
  79.     };
  80.     //send the node a connected graph
  81.     dfs2(start_node, -1);
  82.  
  83.     depth.assign(n, 0);
  84.     max_depth = -INF;
  85.     function<void(ll, ll)> dfs3=[&](ll root , ll parent){
  86.         for(auto it : new_Adj[root]){
  87.             if(it.first==parent) continue;
  88.             depth[it.first] = depth[root] + it.second;
  89.             dfs3(it.first , root);
  90.         }
  91.         max_depth = max(max_depth , depth[root]);
  92.     };
  93.     dfs3(max_node , -1);
  94.  
  95.     cout<<total - max_depth<<endl;
  96. ```
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement