fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // define
  5.  
  6. #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
  7. #define ll long long
  8. #define ld double
  9. #define ii pair<int,int>
  10. #define se second
  11. #define fi first
  12. #define iii pair<int,ii>
  13. #define all(v) v.begin(),v.end()
  14. #define bit(x,i) (((x)>>(i))&1LL)
  15. #define flip(x,i) ((x)^(1LL<<(i)))
  16. #define ms(d,x) memset(d,x,sizeof(d))
  17. #define sitingfake 1
  18. #define orz 1
  19. #define exist __exist
  20. #define ends __ends
  21. #define visit visited
  22. #define left __left
  23. #define right __right
  24.  
  25. //constant
  26.  
  27. const ll mod = 1e9 + 7;
  28. const long long linf = 4557430888798830399;
  29. const int inf = 1061109567;
  30. const int maxarr = 1e6 + 5;
  31. int dx[] = {0 , -1 , 0 , 1};
  32. int dy[] = {-1 , 0 , 1 , 0};
  33.  
  34. template<typename T> bool maximize(T &a, const T &b)
  35. {
  36.     if(a < b) {a = b; return 1;}
  37.     return 0;
  38. }
  39.  
  40. template<typename T> bool minimize(T &a, const T &b)
  41. {
  42.     if(a > b) {a = b; return 1;}
  43.     return 0;
  44. }
  45.  
  46. inline void Plus(ll & a ,ll b)
  47. {
  48.     b %= mod;
  49.     a += b;
  50.     if(a >= mod) a -= mod;
  51.     if(a < 0) a += mod;
  52.     return;
  53. }
  54.  
  55. inline void Mul(ll & a, ll b)
  56. {
  57.     a %= mod; b %= mod;
  58.     a *= b;
  59.     a %= mod;
  60.     return;
  61. }
  62.  
  63. //code
  64.  
  65. const int maxn = 3e5 + 7;
  66.  
  67. int n , q;
  68.  
  69. vector <ii> a[maxn];
  70. ii edges[maxn];
  71.  
  72. int par[maxn];
  73. ll depth[maxn];
  74.  
  75. ll ans[maxn];
  76.  
  77. ll Mi[maxn];
  78.  
  79. vector <int> del;
  80.  
  81. bool d[maxn];
  82.  
  83. void dfs(int u , int p)
  84. {
  85.     for(ii i : a[u])
  86.     {
  87.         int v = i.fi;
  88.         int w = i.se;
  89.         if(v != p)
  90.         {
  91.             depth[v] = depth[u] + w;
  92.             dfs(v , u);
  93.         }
  94.     }
  95. }
  96.  
  97. int get(int u)
  98. {
  99.     if(par[u] < 0) return u;
  100.     return par[u] = get(par[u]);
  101. }
  102.  
  103. void uni(int u , int v)
  104. {
  105.     int pu = get(u);
  106.     int pv = get(v);
  107.  
  108.     if(pu == pv) return;
  109.  
  110.     if(par[pu] > par[pv]) swap(pu , pv);
  111.  
  112.     Mi[pu] = min(Mi[pu] , Mi[pv]);
  113.  
  114.     par[pu] += par[pv];
  115.     par[pv] = pu;
  116. }
  117.  
  118. void solve(void)
  119. {
  120.     cin >> n >> q;
  121.  
  122.     for(int i = 2; i <= n; i++)
  123.     {
  124.         cin >> edges[i].fi >> edges[i].se;
  125.         a[edges[i].fi].push_back(ii(i , edges[i].se));
  126.         a[i].push_back(ii(edges[i].fi , edges[i].se));
  127.     }
  128.  
  129.     for(int i = 1; i <= q; i++)
  130.     {
  131.         int x;
  132.         cin >> x;
  133.         del.push_back(x);
  134.         d[x] = 1;
  135.     }
  136.  
  137.     dfs(1 , -1);
  138.     ms(par , -1);
  139.     Mi[1] = linf;
  140.     for(int i = 2; i <= n; i++)
  141.     {
  142.         if(a[i].size() == 1) Mi[i] = depth[i];
  143.         else Mi[i] = linf;
  144.         par[i] = -1;
  145.     }
  146.  
  147.     for(int i = 2; i <= n; i++)
  148.     {
  149.         if(!d[i])
  150.         {
  151.             uni(edges[i].fi , i);
  152.         }
  153.     }
  154.  
  155.     for(int i = q; i >= 1; i--)
  156.     {
  157.         int p = get(1);
  158.         if(Mi[p] == linf) ans[i] = -1;
  159.         else ans[i] = Mi[p];
  160.         int u = del[i - 1];
  161.         int v = edges[u].fi;
  162.         uni(u , v);
  163.     }
  164.  
  165.     for(int i = 1; i <= q; i++)
  166.     {
  167.         cout << ans[i] << "\n";
  168.     }
  169. }
  170. /**
  171. **/
  172. signed main()
  173. {
  174.    ios_base::sync_with_stdio(0);
  175.    cin.tie(0);
  176.    cout.tie(0);
  177.  
  178.    #define task ""
  179.  
  180.    if(fopen(task".inp","r"))
  181.    {
  182.        freopen(task".inp","r",stdin);
  183.        freopen(task".out","w",stdout);
  184.    }
  185.  
  186.    int tc; tc = 1;
  187.  
  188.    while(tc--) solve();
  189.  
  190.    //execute;
  191. }
  192.  
Success #stdin #stdout 0.01s 17832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rpiqIs
language:
C++14 (clang 8.0)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!