《80分TLE求调》

#include<bits/stdc++.h>
using namespace std;
struct F{
	long long v,nxt;
}e[100010<<1];
struct edge{
	long long Z,X;
}a[1000010];
long long first[100010];
long long n,new_pos;
long long p[100010]; 
long long color[100010];
long long sz[100010],son[100010];
long long cnt[100010]; 
long long ans[100010];
void add(long long a,long long b)
{
	e[++new_pos]=(F){b,first[a]};
	first[a]=new_pos;
}
void dfs1(long long u,long long father)
{
	sz[u]=1;
	son[u]=0;
	int max_size=0;
	for(int i=first[u];i;i=e[i].nxt)
	{
		if(e[i].v==father) continue;
		dfs1(e[i].v,u);
		sz[u]+=sz[e[i].v];
		if(sz[e[i].v]>max_size) 
		{
			max_size=sz[e[i].v];
			son[u]=e[i].v;
		}
	}
}
void calc(long long u,long long father,int val,int sign)
{
	cnt[color[u]]=cnt[color[u]] +sign;
	for(int i=first[u];i;i=e[i].nxt)
	{
		if(e[i].v!=father) calc(e[i].v,u,val,sign);
	}
}
int query(long long u)
{
	int res=0;
	int target=color[u]+1;
	for(int i=target;i<=n;i++) res=res+cnt[i];
	return res;
}

void solve(long long u,long long father,bool keep)
{
	for(int i=first[u];i;i=e[i].nxt)
	{
		if(e[i].v!=father && e[i].v!=son[u]) solve(e[i].v,u,false);
	}
	if(son[u]) solve(son[u],u,true);
	for(int i=first[u];i;i=e[i].nxt)
	{
		if(e[i].v!=father&&e[i].v!=son[u]) calc(e[i].v,u,color[u],1);
	}
	cnt[color[u]]++;
	ans[u] = query(u);
	if(!keep) calc(u,father,color[u],-1);
}
bool cmp(edge x,edge y){
	return x.Z<y.Z;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].Z);
		a[i].X=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++) color[a[i].X]=i;
	for(int i=2;i<=n;i++)
	{
		int u;
		scanf("%d",&u);
		add(u,i);
	}
	dfs1(1,0);
	solve(1,0,1);
	for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
	return 0;
}