Description

n只奶牛构成了一个树形的公司，每个奶牛有一个能力值pi，1号奶牛为树根。
问对于每个奶牛来说，它的子树中有几个能力值比它大的。

Input

n，表示有几只奶牛 n<=100000
接下来n行为1-n号奶牛的能力值pi
接下来n-1行为2-n号奶牛的经理（树中的父亲）

Output

共n行，每行输出奶牛i的下属中有几个能力值比i大

Sample Input

5

804289384

846930887

681692778

714636916

957747794

1

1

2

3

Sample Output

2

0

1

0

0

Solution

线段树合并模板题，$DFS$一遍，然后把儿子的线段树合并到自己身上，查询比自己能力值大的有多少个。

Code

1 #include
     
       2 #include
      
        3 #define N (100009) 4 #define INF (1000000000) 5 using namespace std; 6  7 struct Sgt{
   int ls,rs,val;}Segt[N<<5]; 8 struct Edge{
   int to,next;}edge[N<<1]; 9 int n,x,sgt_num,a[N],ans[N],Root[N];10 int head[N],num_edge;11 12 void add(int u,int v)13 {14     edge[++num_edge].to=v;15     edge[num_edge].next=head[u];16     head[u]=num_edge;17 }18 19 void Update(int &now,int l,int r,int x)20 {21     if (!now) now=++sgt_num;22     Segt[now].val++;23     if (l==r) return;24     int mid=(l+r)>>1;25     if (x<=mid) Update(Segt[now].ls,l,mid,x);26     else Update(Segt[now].rs,mid+1,r,x);27 }28 29 int Query(int now,int l,int r,int l1,int r1)30 {31     if (l>r1 || r
       
        >1,ls=Segt[now].ls,rs=Segt[now].rs;34     return Query(ls,l,mid,l1,r1)+Query(rs,mid+1,r,l1,r1);35 }36 37 void Merge(int &x,int y)38 {39     if (!x || !y) {x|=y; return;}40     Segt[x].val+=Segt[y].val;41     Merge(Segt[x].ls,Segt[y].ls);42     Merge(Segt[x].rs,Segt[y].rs); 43 }44 45 void DFS(int x,int fa)46 {47     for (int i=head[x]; i; i=edge[i].next)48         if (edge[i].to!=fa)49         {50             DFS(edge[i].to,x);51             Merge(Root[x],Root[edge[i].to]);52         }53     ans[x]=Query(Root[x],1,INF,a[x]+1,INF);54 }55 56 int main()57 {58     scanf("%d",&n);59     for (int i=1; i<=n; ++i)60     {61         scanf("%d",&a[i]);62         Update(Root[i],1,INF,a[i]);63     }64     for (int i=2; i<=n; ++i)65     {66         scanf("%d",&x);67         add(i,x); add(x,i);68     }69     DFS(1,0);70     for (int i=1; i<=n; ++i)71         printf("%d\n",ans[i]);72 }