fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <bits/stdc++.h>
  4. #include <stdio.h>
  5. using namespace std;
  6. typedef long long int ll;
  7. vector<ll> adj[500001];
  8.  
  9. ll d[500001];//depth/level
  10. ll it[500001];
  11. ll tt[500001]; 
  12. ll r[500001][2];//subtree[ii] range
  13. ll l[500001];//leaf or not
  14.  
  15.  
  16. vector<ll> qq[500001*2];  //a,b,time,sort_by,ans_order
  17. ll co=-1;
  18. ll cc,dd;
  19.  
  20. ll tree[2][500001*4];
  21. ll lazy[2][500001*4];
  22.  
  23. /*  si -> index of current node in segment tree[ii] 
  24.     ss and se -> Starting and ending indexes of elements for 
  25.                  which current nodes stores sum. 
  26.     us and ue -> starting and ending indexes of update query 
  27.     diff -> which we need to add in the range us to ue */
  28. ll n;
  29. void update(ll si, ll ss,ll se,ll l, ll r, ll value,ll ii) {
  30.   for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  31.     if (l&1) tree[ii][l++] += value;
  32.     if (r&1) tree[ii][--r] += value;
  33.   }
  34. }
  35.  
  36. void update2(ll si, ll ss, ll se, ll us, 
  37.                      ll ue, ll diff,ll ii) 
  38. { 
  39.     // If lazy[ii] value is non-zero for current node of segment 
  40.     // tree[ii], then there are some pending updates. So we need 
  41.     // to make sure that the pending updates are done before 
  42.     // making new updates. Because this value may be used by 
  43.     // parent after recursive calls (See last line of this 
  44.     // function) 
  45.     if (lazy[ii][si] != 0) 
  46.     { 
  47.         // Make pending updates using value stored in lazy[ii] 
  48.         // nodes 
  49.         tree[ii][si] += (se-ss+1)*lazy[ii][si]; 
  50.  
  51.         // checking if it is not leaf node because if 
  52.         // it is leaf node then we cannot go further 
  53.         if (ss != se) 
  54.         { 
  55.             // We can postpone updating children we don't 
  56.             // need their new values now. 
  57.             // Since we are not yet updating children of si, 
  58.             // we need to set lazy[ii] flags for the children 
  59.             lazy[ii][si*2 + 1]   += lazy[ii][si]; 
  60.             lazy[ii][si*2 + 2]   += lazy[ii][si]; 
  61.         } 
  62.  
  63.         // Set the lazy[ii] value for current node as 0 as it 
  64.         // has been updated 
  65.         lazy[ii][si] = 0; 
  66.     } 
  67.  
  68.     // out of range 
  69.     if (ss>se || ss>ue || se<us) 
  70.         return ; 
  71.  
  72.     // Current segment is fully in range 
  73.     if (ss>=us && se<=ue) 
  74.     { 
  75.         // Add the difference to current node 
  76.         tree[ii][si] += (se-ss+1)*diff; 
  77.  
  78.         // same logic for checking leaf node or not 
  79.         if (ss != se) 
  80.         { 
  81.             // This is where we store values in lazy[ii] nodes, 
  82.             // rather than updating the segment tree[ii] itelf 
  83.             // Since we don't need these updated values now 
  84.             // we postpone updates by storing values in lazy[ii][] 
  85.             lazy[ii][si*2 + 1]   += diff; 
  86.             lazy[ii][si*2 + 2]   += diff; 
  87.         } 
  88.         return; 
  89.     } 
  90.  
  91.     // If not completely in rang, but overlaps, recur for 
  92.     // children, 
  93.     ll mid = (ss+se)/2; 
  94.     update(si*2+1, ss, mid, us, ue, diff,ii); 
  95.     update(si*2+2, mid+1, se, us, ue, diff,ii); 
  96.  
  97.     // And use the result of children calls to update this 
  98.     // node 
  99.     tree[ii][si] = tree[ii][si*2+1] + tree[ii][si*2+2]; 
  100. } 
  101.  
  102. ll query(ll ss, ll se, ll p, ll qe, ll si,ll ii)  {
  103.   ll res = 0;
  104.   for (p+=n; p> 0;  p>>= 1) res += tree[ii][p];
  105.   return res;
  106. }
  107. ll query2(ll ss, ll se, ll qs, ll qe, ll si,ll ii) 
  108. { 
  109.     // If lazy[ii] flag is set for current node of segment tree[ii], 
  110.     // then there are some pending updates. So we need to 
  111.     // make sure that the pending updates are done before 
  112.     // processing the sub sum query 
  113.     if (lazy[ii][si] != 0) 
  114.     { 
  115.         // Make pending updates to this node. Note that this 
  116.         // node represents sum of elements in arr[ss..se] and 
  117.         // all these elements must be increased by lazy[ii][si] 
  118.         tree[ii][si] += (se-ss+1)*lazy[ii][si]; 
  119.  
  120.         // checking if it is not leaf node because if 
  121.         // it is leaf node then we cannot go further 
  122.         if (ss != se) 
  123.         { 
  124.             // Since we are not yet updating children os si, 
  125.             // we need to set lazy[ii] values for the children 
  126.             lazy[ii][si*2+1] += lazy[ii][si]; 
  127.             lazy[ii][si*2+2] += lazy[ii][si]; 
  128.         } 
  129.  
  130.         // unset the lazy[ii] value for current node as it has 
  131.         // been updated 
  132.         lazy[ii][si] = 0; 
  133.     } 
  134.  
  135.     // Out of range 
  136.     if (ss>se || ss>qe || se<qs) 
  137.         return 0; 
  138.  
  139.     // At this poll we are sure that pending lazy[ii] updates 
  140.     // are done for current node. So we can return value  
  141.     // (same as it was for query in our previous post) 
  142.  
  143.     // If this segment lies in range 
  144.     if (ss>=qs && se<=qe) 
  145.         return tree[ii][si]; 
  146.  
  147.     // If a part of this segment overlaps with the given 
  148.     // range 
  149.     ll mid = (ss + se)/2; 
  150.     return query(ss, mid, qs, qe, 2*si+1,ii) + 
  151.            query(mid+1, se, qs, qe, 2*si+2,ii); 
  152. } 
  153.  
  154.  ll e[500001];
  155. void build(ll ss, ll se, ll si,ll ii) 
  156. { 
  157.     if (ss > se) 
  158.         return ; 
  159.  
  160.     if (ss == se) 
  161.     { 
  162.         if(1==1){tree[ii][si] = 0;}
  163.         else{tree[ii][si]=it[e[ss]];}//it[ss]; 
  164.         return; 
  165.     } 
  166.     ll mid = (ss + se)/2; 
  167.     build(ss, mid, si*2+1,ii); 
  168.     build(mid+1, se, si*2+2,ii); 
  169.  
  170.     tree[ii][si] = tree[ii][si*2 + 1] + tree[ii][si*2 + 2]; 
  171. } 
  172.  
  173. ll sort_by(const vector<ll>& a,const vector<ll>& b){
  174.  
  175.     if(a[3]!=b[3]){
  176.         return a[3]<b[3];
  177.     }
  178.     return a[1]!=-1 and b[1]==-1;
  179. }
  180.  
  181. void dfs(ll no,ll par,ll lev){
  182.     ll st=0;
  183.     ll i;
  184.     co++;
  185.     d[no]=lev;
  186.  
  187.     r[no][0]=co;
  188.     e[co]=no;
  189.     for(ll j=0;j<adj[no].size();j++){
  190.         i=adj[no][j];
  191.         if(i==par){
  192.             continue;
  193.         }
  194.         st=1;
  195.         //tt[i]+=it[no];
  196.         dfs(i,no,lev+1);
  197.     }
  198.     if(st==0){
  199.      //   tt[no]+=it[no];
  200.         l[no]=1;
  201.     }
  202.     else{
  203.         l[no]=0;
  204.     }
  205.     r[no][1]=co;
  206. }
  207.  
  208. int main() {
  209.     ios_base::sync_with_stdio(false);
  210.     cin.tie(NULL);
  211.     for(int i=0;i<2;i++){
  212. 		for(int j=0;j<2;j++){
  213. 			tree[i][j]=0;
  214. 		}
  215. 	}
  216.     ll t,k,i,j,tot;
  217.     ll q;
  218.     ll a,b;
  219.     cin>>n>>q;
  220.     for(ll i=0;i<n;i++){
  221.         adj[i].clear();
  222.     }
  223.     for(ll i=0;i<n-1;i++){
  224.         cin>>a>>b;
  225.         a-=1;
  226.         b-=1;
  227.  
  228.         adj[a].push_back(b);
  229.         adj[b].push_back(a);
  230.     }
  231.  
  232.     for(ll i=0;i<n;i++){
  233.     //	scanf("%i",&it[i]);
  234.         cin>>it[i];
  235.     }
  236.  
  237.     dfs(0,-1,1);
  238.  
  239.     char s; 
  240.     ll x=0;
  241.     for(ll i=0;i<n;i++){
  242.     	qq[q+i].push_back(i);
  243.     	qq[q+i].push_back(it[i]);
  244.     	qq[q+i].push_back(-1);
  245.     	qq[q+i].push_back(-1-d[i]);
  246.     }
  247.  
  248.     for(ll _=0;_<q;_++){
  249.         cin>>s;
  250.  
  251.         if(s=='?'){
  252.             cin>>a;
  253.             qq[_].push_back(a-1);
  254.             qq[_].push_back(-1);
  255.             qq[_].push_back(_);
  256.             qq[_].push_back(_-d[a-1]);
  257.             qq[_].push_back(x);
  258.             x++;
  259.  
  260.         }
  261.         else{
  262.             cin>>a>>b;
  263.             qq[_].push_back(a-1);
  264.             qq[_].push_back(b);
  265.             qq[_].push_back(_);
  266.             qq[_].push_back(_-d[a-1]);
  267.         }
  268.  
  269.     }
  270.     ll ans[x];
  271. //now to divide queries groups with sane 4th index and then seg tree
  272.     sort(qq,qq+q+n,sort_by);
  273.     ll prev=n+10;
  274.     vector<ll> cur;
  275.     vector<vector<ll>> rem;
  276.  /*   for(ll i=0;i<n;i++){
  277.     	cout<<e[i]<<" ";
  278.     }
  279.     cout<<endl;*/
  280.   /*  for(ll i=0;i<q;i++){
  281.     	for(ll j=0;j<qq[i].size();j++){
  282.     		cout<<qq[i][j]<<" ";
  283.     	}
  284.     	cout<<endl;
  285.     }
  286.     for(ll i=0;i<n;i++){
  287.     	cout<<d[i]<<" ";
  288.     	
  289.     }
  290.     cout<<endl;*/
  291.  
  292.     for(ll i=0;i<q+n;i++){
  293.         cur=qq[i];
  294.         if(cur[3]!=prev and i>0){
  295.             for(ll j=0;j<rem.size();j++){
  296.                 update(0,0,n-1,r[rem[j][0]][0],r[rem[j][0]][1],-rem[j][1],0);
  297.  
  298.             }
  299.             rem.clear();
  300.         }
  301.  
  302.         if(cur.size()==4){
  303.         	cout<<r[cur[0]][0]<<" "<<r[cur[0]][1]<<" "<<cur[1]<<endl;
  304.             update(0,0,n-1,r[cur[0]][0],r[cur[0]][1],cur[1],0);
  305.             update(0,0,n-1,r[cur[0]][0],r[cur[0]][1],cur[1],1);
  306.             rem.push_back(cur);
  307.  
  308.         }
  309.         else{
  310.         	cout<<query(0,n-1,r[cur[0]][0],r[cur[0]][0],0,l[cur[0]])<<" "<<r[cur[0]][0]<<" "<<r[cur[0]][1]<<endl;
  311.         //    for(ll kk=0;kk<4*n;kk++){
  312.         //    	cout<<tree[l[cur[0]]][kk]<<",";
  313.         //    }
  314.          //   cout<<endl;
  315.             ans[cur[4]]=query(0,n-1,r[cur[0]][0],r[cur[0]][0],0,l[cur[0]]);
  316.         }
  317.         prev=cur[3];
  318.  
  319.     }
  320.  
  321.     for(ll i=0;i<x;i++){
  322.         cout<<ans[i]<<endl;
  323.     }
  324.  
  325.  
  326. 	return 0;
  327. }
  328.  
Success #stdin #stdout 0.01s 38760KB
comments (?)
stdin
copy 
5 8
4 3
3 1
5 2
1 2
1 10 4 9 4
+ 1 6
? 3
+ 3 5
? 3
+ 2 2
+ 5 10
? 5
? 4
stdout
copy 
2 2 9
4 4 4
3 4 10
1 2 4
0 4 1
0 4 6
6 1 2
1 2 5
0 1 2
3 4 2
4 4 10
0 4 4
7 2 2
6
0
0
7
https://ideone.com/KUTZ8w
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!