//给定一棵树，求根到每个点的有向链上后缀最大值的个数 //考虑链上的情况，实际上只需要扫右端点的时候维护一个单调栈，单调栈中还剩下的元素个数就是后缀最大值的个数；换到树上我们还需要回溯，考虑每次加入一个点只更改他应该在的位置的数，把新的栈顶传到下一个数，最后再把该位置的数改回来就可以完整地把栈改回来了 #include <iostream> #include <cstdio> using namespace std; const int MAX=1e6+5; int sta[MAX],ans[MAX]; int nxt[MAX<<1],to[MAX<<2],head[MAX],cnt; inline void add(int x,int y){ ++cnt; nxt[cnt]=head[x],to[cnt]=y,head[x]=cnt; ++cnt; nxt[cnt]=head[y],to[cnt]=x,head[y]=cnt; } int value[MAX],fa[MAX]; int n; inline int find(int x,int r){ int l=1,mid,ret=0; while(l<=r){ mid=(l+r)>>1; if(sta[mid]<x)ret=mid,r=mid-1; else l=mid+1; } return ret; } void dfs(int now,int father,int tp){ /*cout<<now<<endl; for(int i=1;i<=tp;i++)cout<<sta[i]<<" "; cout<<endl;*/ ans[now]=tp; for(int aim,i=head[now];i;i=nxt[i]){ aim=to[i]; if(aim!=father){ int pl=find(value[aim],tp); int cpyc=sta[pl],cpytp=tp; if(value[aim]<=sta[tp])sta[++tp]=value[aim]; else sta[pl]=value[aim],tp=pl; dfs(aim,now,tp);// sta[pl]=cpyc,tp=cpytp; } } } signed main(){ scanf("%d",&n); for(int i=2;i<=n;i++)scanf("%d",&fa[i]),add(i,fa[i]); for(int i=1;i<=n;i++)scanf("%d",&value[i]); sta[1]=value[1]; dfs(1,1,1); for(int i=1;i<=n;i++)printf("%d ",ans[i]); return 0; }