codeforces 246 E. Blood Cousins Return （set+dsu on the tree）

E. Blood Cousins Return time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output

Polycarpus got hold of a family tree. The found tree describes the family relations of n people, numbered from 1 to n. Every person in this tree has at most one direct ancestor. Also, each person in the tree has a name, the names are not necessarily unique.

We call the man with a number a a 1-ancestor of the man with a number b, if the man with a number a is a direct ancestor of the man with a number b.

We call the man with a number a a k-ancestor (k > 1) of the man with a number b, if the man with a number b has a 1-ancestor, and the man with a number a is a (k - 1)-ancestor of the 1-ancestor of the man with a number b.

In the tree the family ties do not form cycles. In other words there isn't a person who is his own direct or indirect ancestor (that is, who is an x-ancestor of himself, for some x, x > 0).

We call a man with a number a the k-son of the man with a number b, if the man with a number b is a k-ancestor of the man with a number a.

Polycarpus is very much interested in how many sons and which sons each person has. He took a piece of paper and wrote m pairs of numbers vi, ki. Help him to learn for each pair vi, ki the number of distinct names among all names of the ki-sons of the man with numbervi.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 105) — the number of people in the tree. Next n lines contain the description of people in the tree. The i-th line contains space-separated string si and integer ri (0 ≤ ri ≤ n), where si is the name of the man with a number i, and ri is either the number of the direct ancestor of the man with a number i or 0, if the man with a number i has no direct ancestor.

The next line contains a single integer m (1 ≤ m ≤ 105) — the number of Polycarpus's records. Next m lines contain space-separated pairs of integers. The i-th line contains integers vi, ki (1 ≤ vi, ki ≤ n).

It is guaranteed that the family relationships do not form cycles. The names of all people are non-empty strings, consisting of no more than 20 lowercase English letters.

Output

Print m whitespace-separated integers — the answers to Polycarpus's records. Print the answers to the records in the order, in which the records occur in the input.

Examples input 6 pasha 0 gerald 1 gerald 1 valera 2 igor 3 olesya 1 5 1 1 1 2 1 3 3 1 6 1 output 2 2 0 1 0 input 6 valera 0 valera 1 valera 1 gerald 0 valera 4 kolya 4 7 1 1 1 2 2 1 2 2 4 1 5 1 6 1 output 1 0 0 0 2 0 0

题解：set+dsu on the tree

STL大法好！对于每个深度开一个set记录每种颜色的信息。

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<set> #include<map> #define N 200003 using namespace std; int n,m,size[N],son[N],mark[N],deep[N],tot,col[N]; int ans[N],point[N],head[N],v[N],nxt[N],next[N],u[N],num[N]; map<string,int> mp; set<int> dep[N]; 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 z){ tot++; next[tot]=head[x]; head[x]=tot; u[tot]=y; num[tot]=z; } void solve(int x,int fa) { size[x]=1; deep[x]=deep[fa]+1; for (int i=point[x];i;i=nxt[i]){ if (v[i]==fa) continue; solve(v[i],x); size[x]+=size[v[i]]; if (size[son[x]]<size[v[i]]) son[x]=v[i]; } } void calc(int x,int fa) { dep[deep[x]].insert(col[x]); for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!mark[v[i]]) calc(v[i],x); } void clear(int x,int fa) { dep[deep[x]].clear(); for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!mark[v[i]]) clear(v[i],x); } void dfs(int x,int fa,bool k) { for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&v[i]!=son[x]) dfs(v[i],x,0); if (son[x]) dfs(son[x],x,1),mark[son[x]]=1; calc(x,fa); for (int i=head[x];i;i=next[i]) { int t; if((t=deep[x]+u[i])>100001) continue; ans[num[i]]=dep[t].size(); } if (son[x]) mark[son[x]]=0; if (!k) clear(x,fa); } int main() { freopen("a.in","r",stdin); scanf("%d",&n); string s; int root=0; int cnt=0; for (int i=1;i<=n;i++) { cin>>s; int x; scanf("%d",&x); add(x,i); if (!mp[s]) mp[s]=++cnt; col[i]=mp[s]; } //for (int i=1;i<=n;i++) cout<<col[i]<<" "; //cout<<endl; scanf("%d",&m); tot=0; for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); build(x,y,i); } solve(root,0); dfs(root,0,0); for (int i=1;i<=m;i++) printf("%d\n",ans[i]); }