题目

#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long n,m,hs[100010],sz[100010],l[100010],d[100010],dep[100010],r[100010],dfn[100010],id[100010],ans[100010],num,mx,u,v;
vector<int> e[100010],as[100010],nu[100010],sta;
map<string,int> s;
string c[100010],st;
void dfs1(ll u,ll fa)
{
	dep[u]=dep[fa]+1;
	sz[u]=1;
	hs[u]=-1;
	dfn[++num]=u;
	l[u]=num;
	for(int v:e[u])
	{
		if(v==fa)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(hs[u]==-1||sz[hs[u]]<sz[v])hs[u]=v;
	}
	r[u]=num;
}
void add(ll x)
{
	if(s[c[x]]==0)d[dep[x]]++;
	s[c[x]]++;
}
void del(ll x)
{
	s[c[x]]--;
}
void dfs2(ll u,ll fa,bool ok)
{
	for(int v:e[u])
	{
		if(v==fa||v==hs[u])continue;
		dfs2(v,u,0);
	}
	if(hs[u]!=-1)dfs2(hs[u],u,1);
	for(int v:e[u])
	{
		if(v==fa||v==hs[u])continue;
		for(int i=l[v];i<=r[v];i++)add(dfn[i]);
	}
	add(u);
	for(int i=0;i<as[u].size();i++)ans[nu[u][i]]+=d[as[u][i]+dep[u]];
	if(ok==0)
	{
		for(int i=l[u];i<=r[u];i++)del(dfn[i]);
		memset(d,0,sizeof(d));
	}
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>c[i];
		scanf("%lld",&u);
		e[u].push_back(i);
		e[i].push_back(u);
		if(u==0)sta.push_back(i);
	}
	scanf("%lld",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&u,&v);
		as[u].push_back(v);
		nu[u].push_back(i); 
	}
	
	for(int i:sta)dfs1(i,0);
	for(int i:sta)dfs2(i,0,0);
	for(int i=1;i<=m;i++)printf("%lld ",ans[i]);
	return 0;
}

```#9 TLE