Guest User

F - No Link, Cut Tree!

a guest
Aug 29th, 2017
202
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long int
  6. #define inf 0x3f3f3f3f
  7. #define pb push_back
  8. #define mk make_pair
  9. #define fi first
  10. #define se second
  11. #define ii pair<int, int>
  12. #define all(x) (x).begin(), (x).end()
  13. #define N 1000007
  14.  
  15. vector<int>adj[N], vt[N];
  16. int w[N], h[N];
  17.  
  18. vector<int>go(int curr){
  19.     if(vt[curr].size())return vt[curr];
  20.     vector<int>v[3], ret;
  21.     for(int i=0; i<adj[curr].size(); i++){
  22.         v[i]=go(adj[curr][i]);
  23.     }
  24.     ret.pb(w[curr]);
  25.     for(int i=0; i<max(v[0].size(), v[1].size()); i++){
  26.         int a=0, b=0;
  27.         if(i<v[0].size())a=v[0][i];
  28.         if(i<v[1].size())b=v[1][i];
  29.         ret.pb(a+b);
  30.        
  31.     }
  32.     return vt[curr]=ret;
  33. }
  34.  
  35. void go(int curr, int t){
  36.     h[curr]=t;
  37.     for(int i=0; i<adj[curr].size(); i++)go(adj[curr][i], t+1);
  38. }
  39.  
  40. int main(int argc, char const *argv[]){
  41.     ios::sync_with_stdio(false);
  42.     int n, q, ww;
  43.     cin >> n >> q >> ww;
  44.     w[1]=ww;
  45.     for(int i=0; i<n-1; i++){
  46.         int u, v, ww;
  47.         cin >> u >> v >> ww;
  48.         adj[v].pb(u);
  49.         w[u]=ww;
  50.     }
  51.     vt[1]=go(1);
  52.     go(1, 0);
  53.     while(q--){
  54.         int u;
  55.         cin >> u;
  56.         int ans=0, cc=0;
  57.         for(int x=0, i=0; i<vt[1].size(); i++){
  58.             x=0;
  59.             if(i>=h[u] && cc<vt[u].size()) x=vt[u][cc++];
  60.             ans=max(ans, vt[1][i]-x);
  61.         }
  62.         cout << ans << endl;
  63.     }
  64.     return 0;
  65. }
RAW Paste Data