树链剖分|codeforces 208 E. Blood Cousins (dsu on the tree)


E. Blood Cousins time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Polycarpus got hold of a family relationship tree. The tree describes family relationships of n people, numbered 1 through n. Each person in the tree has no more than one parent.
Let's call person a a 1-ancestor of person b, if a is the parent of b.
Let's call person a a k-ancestor (k?>?1) of person b, if person b has a 1-ancestor, and a is a (k?-?1)-ancestor of b's 1-ancestor.
Family relationships don't form cycles in the found tree. In other words, there is no person who is his own ancestor, directly or indirectly (that is, who is an x-ancestor for himself, for some x, x?>?0).
Let's call two people x and y (x?≠?y) p-th cousins (p?>?0), if there is person z, who is a p-ancestor of x and a p-ancestor of y.
Polycarpus wonders how many counsins and what kinds of them everybody has. He took a piece of paper and wrote m pairs of integersvi, pi. Help him to calculate the number of pi-th cousins that person vi has, for each pair vi, pi.
Input The first input line contains a single integer n (1?≤?n?≤?105) — the number of people in the tree. The next line contains n space-separated integers r1,?r2,?...,?rn, where ri (1?≤?ri?≤?n) is the number of person i's parent or 0, if person i has no parent. It is guaranteed that family relationships don't form cycles.
The third line contains a single number m (1?≤?m?≤?105) — the number of family relationship queries Polycarus has. Next m lines contain pairs of space-separated integers. The i-th line contains numbers vi, pi (1?≤?vi,?pi?≤?n).
Output Print m space-separated integers — the answers to Polycarpus' queries. Print the answers to the queries in the order, in which the queries occur in the input.
Examples input

6 0 1 1 0 4 4 7 1 1 1 2 2 1 2 2 4 1 5 1 6 1

output
0 0 1 0 0 1 1






题目大意:给出一棵家谱树,定义向上走k步到达的节点为该点的k-ancestor.每次询问与v同P-ancestor的节点有多少个。
题解:dsu on the tree
将问题转换成p-ancestor的子树有多少个深度为deep[v]的节点。

#include #include #include #include #include #define N 200003 using namespace std; int tot,point[N],v[N],nxt[N],next[N],head[N],c[N],u[N],mark[N]; int deep[N],size[N],son[N],fa[N][20],mi[20],ans[N],num[N],n,m; void add(int x,int y) { tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; } void build(int x,int y,int i) { tot++; next[tot]=head[x]; head[x]=tot; u[tot]=y; c[tot]=i; } void solve(int x,int f) { deep[x]=deep[f]+1; size[x]=1; for (int i=1; i<=17; i++) { if (deep[i]-mi[i]<0) continue; fa[x][i]=fa[fa[x][i-1]][i-1]; } for (int i=point[x]; i; i=nxt[i]){ if(v[i]==f) continue; fa[v[i]][0]=x; solve(v[i],x); size[x]+=size[v[i]]; if (size[son[x]]>i)&1) x=fa[x][i]; return x; } void change(int x,int f,int val) { num[deep[x]]+=val; for (int i=point[x]; i; i=nxt[i]) if (v[i]!=f&&!mark[v[i]]) change(v[i],x,val); } void dfs(int x,int f,bool k) { for (int i=point[x]; i; i=nxt[i]) if (v[i]!=f&&v[i]!=son[x]) dfs(v[i],x,0); if (son[x]) dfs(son[x],x,1),mark[son[x]]=1; change(x,f,1); for (int i=head[x]; i; i=next[i]) ans[c[i]]=num[u[i]]; if (son[x]) mark[son[x]]=0; if (!k) change(x,f,-1); } int main() { freopen("a.in","r",stdin); scanf("%d",&n); for (int i=1; i<=n; i++) { int x; scanf("%d",&x); add(x,i); } solve(0,0); scanf("%d",&m); tot=0; for (int i=1; i<=m; i++) { int x,p; scanf("%d%d",&x,&p); if (deep[x]-2【树链剖分|codeforces 208 E. Blood Cousins (dsu on the tree)】



    推荐阅读