Codeforce 685 B. Kay and Snowflake 解析(思維、DFS、DP、重心)

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

題目
給你一棵樹，要求你求出每棵子樹的重心。

前言

完全不知道我怎麼想到的

想法

首先會感覺是樹狀DP，並且狀態是每個子樹的重心。
在建重心剖分樹的時候，我們找根為$v$的樹的重心的方法是看看目前節點有沒有大小大於目前樹的一半($size[v]/2$)的子樹(令根為$u$)，並且繼續看看這棵子樹有沒有大小大於$size[v]/2$的子樹(注意，不是$size[u]$)，如果沒有的話，$u$就是重心。
注意到，由於$u$的重心代表的點是子樹大小都小於$size[u]$的點，只要我們慢慢由這個重心往上回朔($u$的重心$\rightarrow$$u$的重心的父節點)，總能找到所有子樹大小都小於且最接近$size[v]$的點，而那就是答案了。
需要順便維護每個點最大的子樹的大小在$mx[]$裡，加快運算。
由於我們是從$u$的重心開始找，所以即使整棵樹退化成一個鍊，我們每次也只需要往上移一格就找到答案了。而更一般的狀況我猜想複雜度接近$O(n\lg n)$，但暫時還不確定怎麼證明Orz

程式碼:

const int _n=3e5+10;  
int t,n,q,v,p,dp[_n],sz[_n],mx[_n],fa[_n];  
VI G[_n];  
void dfsSz(int v,int faa){  
  fa[v]=faa,sz[v]=1;  
  for(int u:G[v])if(u!=faa)dfsSz(u,v),sz[v]+=sz[u],mx[v]=max(mx[v],sz[u]);  
}  
void dfs(int v,int faa){  
  for(int u:G[v])if(u!=faa)dfs(u,v);  
  for(int u:G[v])if(u!=faa and sz[u]>sz[v]/2){  
    u=dp[u];while(mx[u]<=sz[v]/2)dp[v]=u,u=fa[u];  
    return;  
  }  
  dp[v]=v;  
}  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>q;rep(i,2,n+1){cin>>p;G[i].pb(p),G[p].pb(i);}  
  dfsSz(1,0),mx[0]=sz[1],dfs(1,0);  
  while(q--){  
    cin>>v;cout<<dp[v]<<'\n';  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission