[文章目录]
Description
n只奶牛构成了一个树形的公司，每个奶牛有一个能力值pi，1号奶牛为树根。问对于每个奶牛来说，它的子树中有几个能力值比它大的。n<=100000
记录每个节点dfs入栈序，然后将节点按照p排序，从大到小加点。将比节点权值大的先加入，然后查询子树区间和。树状数组维护。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
struct node
{
int w,id;
}a[101000];
int head[101000],nxt[101000],to[101000],cnt;
void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
int in[101000],out[101000],tot;
void dfs(int x)
{
in[x]=++tot;
for(int i=head[x];i;i=nxt[i])
dfs(to[i]);
out[x]=tot;
}
bool cmp(node x,node y){return x.w>y.w;}
int ans[101000],f[101000];
void fix(int x) {while(x>0) f[x]++,x-=-x&x;}
int query(int x)
{
int re=0;
while(x<=tot) re+=f[x],x+=-x&x;
return re;
}
int main()
{
scanf("%d",&n);
int i,x;
for(i=1;i<=n;++i) scanf("%d",&a[i].w),a[i].id=i;
for(i=2;i<=n;++i)
{
scanf("%d",&x);
add(x,i);
}
dfs(1);
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;++i)
{
ans[a[i].id]=query(in[a[i].id])-query(out[a[i].id]+1);
fix(in[a[i].id]);
}
for(i=1;i<=n;++i) printf("%d\n",ans[i]);
return 0;
}