挺简单的一道树链剖分，直接上就好了。 不能像区间和那样传标记,因为可能标记会被重复标记.
#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=6e5+5; int n,m; int head[N],next[N],go[N],val[N]; int siz[N],dep[N],fa[N]; int pos[N],top[N],v[N]; int tot=0,sz; struct node { int l,r,sum,lazy; }t[3000000]; inline void add(int x,int y) { go[++tot]=y; next[tot]=head[x]; head[x]=tot; } inline void dfs1(int x) { siz[x]=1; for(int i=head[x];i;i=next[i]) { int v=go[i]; if (v!=fa[x]) { dep[v]=dep[x]+1; fa[v]=x; dfs1(v); siz[x]+=siz[v]; } } } inline void dfs2(int x,int chain) { int k=0; sz++; pos[x]=sz; top[x]=chain; for(int i=head[x];i;i=next[i]) { int v=go[i]; if (v!=fa[x]&&siz[v]>siz[k]) k=v; } if (!k)return; dfs2(k,chain); for(int i=head[x];i;i=next[i]) { int v=go[i]; if (v!=fa[x]&&k!=v) { dfs2(v,v); } } } inline void build(int x,int l,int r) { t[x].l=l,t[x].r=r; t[x].sum=t[x].lazy=0; if (l==r)return; int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); } inline void pushdown(int x) { if (t[x].l==t[x].r)return; /*if (t[x].lazy) { t[x<<1].sum++; t[x<<1|1].sum++; t[x<<1].lazy=1,t[x<<1|1].lazy=1; t[x].lazy=0; }*/ if (t[x].sum) { t[x<<1].sum+=t[x].sum; t[x<<1|1].sum+=t[x].sum; t[x].sum=0; } } inline void change(int x,int l,int r) { pushdown(x); if (t[x].l==l&&t[x].r==r) { //t[x].lazy=1; t[x].sum++; return; } int mid=(t[x].l+t[x].r)>>1; if (r<=mid)change(x<<1,l,r); else if (l>mid)change(x<<1|1,l,r); else { change(x<<1,l,mid); change(x<<1|1,mid+1,r); } //t[x].sum=t[x<<1].sum+t[x<<1|1].sum; } inline int query(int x,int pos) { if (t[x].l==t[x].r)return t[x].sum; int mid=(t[x].l+t[x].r)>>1;pushdown(x); if (pos<=mid)return query(x<<1,pos); else return query(x<<1|1,pos); } inline void solve(int x,int y) { while(top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]])swap(x,y); change(1,pos[top[x]],pos[x]); x=fa[top[x]]; } if (dep[x]>dep[y])swap(x,y); change(1,pos[x],pos[y]); } int main() { scanf("%d",&n); fo(i,1,n)scanf("%d",&v[i]); fo(i,1,n-1) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs1(1); dfs2(1,1); build(1,1,n); fo(i,1,n-1) { solve(v[i],v[i+1]); } fo(i,1,n) if (i==v[1]) printf("%d\n",query(1,pos[i])); else printf("%d\n",query(1,pos[i])-1); }