Codeforce 383 C. Propagating tree 解析(思維、DFS順序、BIT、線段樹)

今天我們來看看CF383C
題目連結

題目
略，請直接看原題

前言

DFS順序的題目之前還真的完全沒用過。

想法

一開始的想法可能會是每次查詢都往祖先看val是多少，然後取個正負號加上去。然而這棵樹很有可能退化成一條鍊，造成查詢複雜度到達$O(n)$。
而我們仔細觀察一下會發現，如果我們對於每個節點$x$，能夠得知其所有祖先節點的$val$的和，就可以快速解決問題。
我們馬上可以想到BIT或者線段樹，然而這兩個結構都是用在數列上的，要把這些結構應用到樹上就必須先DFS一次，以剛開始看一個節點的時間$++t$作為這個節點的$id$，而當這個節點的子節點都處理結束以後的時間$t$當作這個節點的結束時間(也就是其最後一個子樹節點的$id$)。這樣一來，一個節點$u$的子樹的節點$id$就會在$[id[u],ed[u]]$區間內。
並且注意到這題我們需要分別考慮深度為奇數和偶數的節點，也就是造兩個BIT。
假設目前有個奇數深度的點$x$要加$val$，我們就會在奇數BIT上的$id[x]$加上$val$，並且在$ed[x]+1$減掉$val$。而如果點$x$有子節點，那麼會在偶數BIT上的$id[x]+1$減掉$val$，並且在$ed[x]+1$加上$val$。(也就是說，兩個BIT中都有一半的點是用不到的)
如此一來，查詢$x$的值時只要先判斷$x$的深度，接著就能夠看看要到哪個$BIT$查詢答案。

程式碼:

const int _n=2e5+10;  
int _,__,t,n,m,x,u,v,vv,a[_n],val[_n],id[_n],ed[_n],d[_n],n1,n2;  
VI G[_n];  
class BIT{  
  public:  
  int nn;ll t[_n];  
  void update(int x,int val){while(x<=nn)t[x]+=val,x+=(x&-x);}  
  //這模板是1-base，而且update是把修改量加上去  
  ll query(int x){ll res=0;while(x>0){res+=t[x],x-=(x&-x);}return res;}  
  void init(int n_){nn=n_;}  
};  
BIT bits[2];  
void dfs(int u,int fa){  
  d[u]=d[fa]+1,id[u]=++t;  
  for(int v:G[u])if(v!=fa)dfs(v,u);  
  ed[u]=t;  
}  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>m;rep(i,1,n+1)cin>>a[i]; rep(i,0,n-1){cin>>u>>v;G[u].pb(v),G[v].pb(u);} dfs(1,0);  
  rep(i,0,2)bits[i].init(n+1); while(m--){  
    cin>>_>>x;if(_==1){  
      cin>>vv;bits[d[x]&1].update(id[x],vv),bits[d[x]&1].update(ed[x]+1,-vv);  
      vv=-vv;if(id[x]<ed[x])bits[!(d[x]&1)].update(id[x]+1,vv),bits[!(d[x]&1)].update(ed[x]+1,-vv);  
    }else cout<<bits[d[x]&1].query(id[x])+a[x]<<'\n';  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission