fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll start[200001]; 
  5. ll endd[200001]; 
  6.  
  7. vector<ll>ans; 
  8. vector<ll>vect[200001]; 
  9. ll visited[200001]; 
  10. ll level[200001];
  11. ll arr[200001];
  12. ll b;
  13. //
  14. void dfs(int node,int par,int lvl)
  15. {
  16.     b++; 
  17.     start[node]=b; 
  18.     ans.push_back(node); 
  19.     level[node]=lvl;
  20.     for(auto child:vect[node])
  21.     {
  22.         if(child!=par)
  23.         {
  24.             dfs(child,node,lvl+1);
  25.         }
  26.     }
  27.     endd[node]=b; 
  28. }
  29. //
  30. void solve(ll x)
  31. {
  32.       if(start[x]!=endd[x]) 
  33.         { 
  34.             for(int j=start[x]+1;j<=endd[x];j++) 
  35.             { if(visited[ans[j-1]]==0){
  36.                 if((level[x]-level[ans[j-1]])%2==0)
  37.                    {arr[x]+=arr[ans[j-1]];
  38.                     arr[ans[j-1]]=0;
  39.  
  40.                    visited[ans[j-1]]=1;
  41.                    }
  42.             }
  43.             } 
  44.  
  45.         } 
  46. }
  47.  
  48. int main()
  49. {
  50.  ll t; cin>>t;
  51.  while(t--)
  52.  {
  53.      ll n,q;  cin>>n>>q;
  54.  
  55.      for(ll i =1;i<=n;i++)
  56.      {
  57.          vect[i].clear();
  58.          visited[i]=0;
  59.          level[i]=0;
  60.          arr[i]=0;
  61.          ans.clear();
  62.          start[i]=0;
  63.          endd[i]=0;
  64.  
  65.      }
  66.      for(ll i=1;i<=n;i++) cin>>arr[i];
  67.      //
  68.      for(int i=1;i<n;i++)
  69.      {
  70.          int a,b;
  71.          cin>>a>>b;
  72.          vect[a].push_back(b);
  73.          vect[b].push_back(a);
  74.      }
  75.      //
  76.      b=0;
  77.      dfs(1,-1,0);
  78.      //
  79.      while(q--)
  80.      {
  81.          ll x; cin>>x;
  82.          solve(x);
  83.  
  84.      }
  85.         for(int i=1;i<=n;i++)
  86.      {
  87.          cout<<arr[i]<<" ";
  88.      }
  89.      cout<<endl;
  90.  
  91.  
  92.  }
  93.  
  94. }
Success #stdin #stdout 0s 8296KB
comments ()
stdin 
1
8 1
1 1 1 1 1 1 1 1
1 2
2 3
3 4
4 7
2 5
5 6
6 8
5
1
stdout 
1 1 1 1 2 1 1 0
https://ideone.com/p1lkRA
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

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!