fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. typedef long long ll;
  5. #define PB push_back
  6. const ll M = 2e5+7;
  7.  
  8. vector<vector<ll> > edg(M), levelOrder(M), BIT(M);
  9. ll val[M], llime[M], outTime[M], nodeLevel[M];
  10. bool visited[M];
  11.  
  12. ll bitSum(vector<ll> &arr, ll pos){
  13.     ll sum = 0;
  14.     while(pos>0){
  15.         sum += arr[pos];
  16.         pos -= (pos & (-pos));
  17.     }
  18.     return sum;
  19. }
  20.  
  21. void bitUpdate(vector<ll> &arr, ll pos, ll val){
  22.     while(pos<(ll)arr.size()){
  23.         arr[pos] += val;
  24.         pos += (pos & (-pos));
  25.     }
  26. }
  27.  
  28. bool compllime(ll node1, ll node2){
  29.     return llime[node1]<llime[node2];
  30. }
  31.  
  32. bool compOutTime(ll node1, ll node2){
  33.     return outTime[node1]<outTime[node2];
  34. }
  35.  
  36. ll dfs(ll node, ll level, ll time){
  37.  
  38.     visited[node] = true;
  39.     nodeLevel[node] = level;
  40.     levelOrder[level].PB(node);
  41.     llime[node] = time;
  42.  
  43.     for (auto x : edg[node]){
  44.         if (visited[x])
  45.             continue;
  46.         time = dfs(x, level+1, time+1);
  47.     }
  48.     return outTime[node] = time + 1;
  49. }
  50.  
  51. int main(){
  52.     fast;
  53.     ll n,a,b;
  54.     cin>>n;
  55.     for (ll i = 1; i < n; i++){
  56.         cin>>a>>b;
  57.         edg[a].PB(b);
  58.         edg[b].PB(a);
  59.     }
  60.     for (ll i = 1; i <= n; i++)
  61.         cin>>val[i];
  62.     dfs(1,0,0);
  63.  
  64.     for (ll i = 0; ; i++){
  65.         if (levelOrder[i].size() == 0)
  66.             break;
  67.         sort(levelOrder[i].begin(), levelOrder[i].end(), compllime);
  68.         BIT[i].resize(levelOrder[i].size() + 1);
  69.         for (ll j = 0; j<(ll)levelOrder[i].size(); j++){
  70.             bitUpdate(BIT[i], j+1, val[levelOrder[i][j]] );
  71.         }
  72.     }
  73.     ll q; 
  74.     cin>>q; 
  75.     while(q--){
  76.         ll t, x, y;
  77.         cin>>t>>x>>y;
  78.         if (t == 1){
  79.             ll pos = lower_bound(levelOrder[nodeLevel[x]].begin(), levelOrder[nodeLevel[x]].end(), x, compllime) - levelOrder[nodeLevel[x]].begin();
  80.             bitUpdate(BIT[nodeLevel[x]], pos+1, -val[x]);
  81.             val[x] = y;
  82.             bitUpdate(BIT[nodeLevel[x]], pos+1, val[x]);
  83.         }
  84.         else{
  85.             a = lower_bound(levelOrder[nodeLevel[x]+y].begin(), levelOrder[nodeLevel[x]+y].end(), x, compllime) - levelOrder[nodeLevel[x]+y].begin();
  86.             b = upper_bound(levelOrder[nodeLevel[x]+y].begin(), levelOrder[nodeLevel[x]+y].end(), x, compOutTime) - levelOrder[nodeLevel[x]+y].begin() - 1;
  87.             ll ans = bitSum(BIT[nodeLevel[x]+y], b+1) - bitSum(BIT[nodeLevel[x]+y], a);
  88.             cout<<ans<<"\n";
  89.         }
  90.     }
  91.     return 0;
  92. }
Runtime error #stdin #stdout 0s 17124KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aiU4wS
language:
C++14 (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!