[Codeforces] 208E. Blood Cousins

題目連結:http://codeforces.com/problemset/problem/208/E

---

稍微轉化一下問題就可以得到問節點$i$的子節點們深度為$d$的有那些，轉法也很簡單，對於一組詢問$(v, p)$就直接變成，對於$v$的$p$倍祖先問在$dep[v]$的數字有哪些(問一個人的$p$倍祖先可以直接用個倍增法做到)。轉化成這樣後就可以直接開個map維護每個深度為$k$時有幾個，然後要合併兩子樹就啟發式合併就好了。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
typedef pair<int,int> PII;
#define PB push_back
#define FF first
#define SS second

class K_anc{
	private:
		vector<int> G[N];
		int anc[N][20];
		void dfs(int w, int f){
			anc[w][0]=f;
			for(auto i: G[w]) if(i!=f)
				dfs(i, w);
		}
	public:
		inline void AddEdge(int u, int v){
			G[u].PB(v);
			G[v].PB(u);
		}
		void solve(int r, int maxn){
			dfs(r, r);
			for(int j=1;j<20;j++) for(int i=0;i<maxn;i++){
				anc[i][j] = anc[anc[i][j-1]][j-1];
			}
		}
		int query(int a, int k){
			for(int i=0;i<20;i++) if(k & (1<<i))
				a=anc[a][i];
			return a;
		}

} anc;

vector<int> G[N];
vector<PII> que[N];
int dep[N], ans[N];

void dfs(int,map<int,int>&);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	dep[0]=0;
	for(int i=1;i<=n;i++){
		int p; cin>>p;
		G[p].PB(i);
		anc.AddEdge(p, i);
		dep[i]=dep[p]+1;
	}
	anc.solve(0, n+1);
	int q; cin>>q;
	for(int i=0;i<q;i++){
		int v, p; cin>>v>>p;
		int f = anc.query(v, p);
		if(f!=0) que[f].PB({dep[v], i});
	}
	map<int,int> mp;
	dfs(0, mp);
	for(int i=0;i<q;i++) cout<<ans[i]<<" \n"[i==q-1];
	return 0;
}

void dfs(int w, map<int,int>& mp){
	mp[dep[w]]++;
	for(auto i: G[w]){
		map<int,int> temp;
		dfs(i, temp);
		if(temp.size() > mp.size()) swap(mp, temp);
		for(auto data: temp) mp[data.FF]+=data.SS;
	}
	for(auto q: que[w]) ans[q.SS] = mp[q.FF]-1;
}