fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define bit(n,i) ((n>>i) &1)
  4. #pragma GCC optimize("O3,unroll-loops")
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define maxn 200005
  7. #define fi first
  8. #define se second
  9. #define int long long
  10.  
  11. using namespace std;
  12.  
  13. ll sz[maxn], high[maxn], par[maxn];
  14. ll heavy[maxn], head[maxn], pos[maxn];
  15. ll n,q,cur=0;
  16. vector<int> adj[maxn];
  17.  
  18. struct Node{
  19.     ll sum;
  20.     int cnt1;
  21.     ll lazy;   
  22.     bool flip;
  23. } st[4*maxn];
  24.  
  25. void apply_add(int id,int l,int r,ll x){
  26.     int len=r-l+1;
  27.     st[id].sum += x*(len - 2*st[id].cnt1);
  28.     st[id].lazy += x;
  29. }
  30.  
  31. void apply_flip(int id,int l,int r){
  32.     int len=r-l+1;
  33.     st[id].cnt1 = len - st[id].cnt1;
  34.     st[id].flip ^= 1;
  35.     st[id].lazy = -st[id].lazy;
  36. }
  37.  
  38. void push(int id,int l,int r){
  39.     int m=(l+r)>>1;
  40.  
  41.     if(st[id].flip){
  42.         apply_flip(id<<1,l,m);
  43.         apply_flip(id<<1|1,m+1,r);
  44.         st[id].flip=0;
  45.     }
  46.  
  47.     if(st[id].lazy){
  48.         apply_add(id<<1,l,m,st[id].lazy);
  49.         apply_add(id<<1|1,m+1,r,st[id].lazy);
  50.         st[id].lazy=0;
  51.     }
  52. }
  53.  
  54. void pull(int id){
  55.     st[id].sum = st[id<<1].sum + st[id<<1|1].sum;
  56.     st[id].cnt1 = st[id<<1].cnt1 + st[id<<1|1].cnt1;
  57. }
  58.  
  59. void update(int id,int l,int r,int u,int v,ll x){
  60.     if(l>r || u>v || l>v || r<u) return;
  61.     if(u<=l && r<=v){
  62.         apply_add(id,l,r,x);
  63.         apply_flip(id,l,r);
  64.         return;
  65.     }
  66.     push(id,l,r);
  67.     int m=(l+r)>>1;
  68.     update(id<<1,l,m,u,v,x);
  69.     update(id<<1|1,m+1,r,u,v,x);
  70.     pull(id);
  71. }
  72.  
  73. ll get(int id,int l,int r,int u,int v){
  74.     if(l>r || u>v || l>v || r<u) return 0;
  75.     if(u<=l && r<=v) return st[id].sum;
  76.     push(id,l,r);
  77.     int m=(l+r)>>1;
  78.     return get(id<<1,l,m,u,v) + get(id<<1|1,m+1,r,u,v);
  79. }
  80.  
  81. void dfs(int u,int p){
  82.     sz[u]=1;
  83.     par[u]=p;
  84.     int mx=0;
  85.  
  86.     for(int v:adj[u]){
  87.         if(v==p) continue;
  88.         high[v]=high[u]+1;
  89.         dfs(v,u);
  90.         sz[u]+=sz[v];
  91.         if(sz[v]>mx){
  92.             mx=sz[v];
  93.             heavy[u]=v;
  94.         }
  95.     }
  96. }
  97.  
  98. void HLD(int u,int h){
  99.     head[u]=h;
  100.     pos[u]=++cur;
  101.  
  102.     if(heavy[u]) HLD(heavy[u],h);
  103.  
  104.     for(int v:adj[u]){
  105.         if(v!=par[u] && v!=heavy[u]){
  106.             HLD(v,v);
  107.         }
  108.     }
  109. }
  110.  
  111.  
  112. void update_path(int u,int v,int x){
  113.     while(head[u]!=head[v]){
  114.         if(high[head[u]] < high[head[v]]) swap(u,v);
  115.         update(1,1,n,pos[head[u]],pos[u],x);
  116.         u=par[head[u]];
  117.     }
  118.     if(high[u]>high[v]) swap(u,v);
  119.     update(1,1,n,pos[u],pos[v],x);
  120. }
  121.  
  122.  
  123. signed main(){
  124.     itachi
  125.     cin>>n>>q;
  126.  
  127.     for(int i=1;i<n;i++){
  128.         int u,v; cin>>u>>v;
  129.         adj[u].push_back(v);
  130.         adj[v].push_back(u);
  131.     }
  132.  
  133.     dfs(1,0);
  134.     HLD(1,1);
  135.  
  136.     while(q--){
  137.         int opt; cin>>opt;
  138.         if(opt==1){
  139.             int u,v,x;
  140.             cin>>u>>v>>x;
  141.             update_path(u,v,x);
  142.         }else{
  143.             int v; cin>>v;
  144.             cout<<get(1,1,n,pos[v],pos[v])<<"\n";
  145.         }
  146.     }
  147.     return 0;
  148. }
  149.  
Success #stdin #stdout 0.01s 15832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FQYKL6
language:
C++14 (gcc 8.3)
created:
1 day 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!