裸题了，我不会告诉你我调了一个小时
常规操作的啦,不细说了
#include<bits/stdc++.h> #define ls(x) x<<1 #define rs(x) x<<1|1 using namespace std; const int N=12e5+6; int m,n,k,l,root,res,cnt,tot,from,to; int size[N],top[N],v[N],vt[N],fa[N],sum[N<<2],lg[N<<2],head[N],dep[N],id[N],son[N]; int a[N]; int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();} return x*f; } struct edge { int nx,to; } e[N]; void add_edge(int a,int b) { cnt++;e[cnt].nx=head[a];e[cnt].to=b;head[a]=cnt; cnt++;e[cnt].nx=head[b];e[cnt].to=a;head[b]=cnt; } void push_up(int p) { sum[p]=sum[ls(p)]+sum[rs(p)]; } void build(int p,int l,int r) { if (l==r) { sum[p]=vt[l]; return; } int mid=(l+r)>>1; build(ls(p),l,mid); build(rs(p),mid+1,r); push_up(p); } void push_down(int p,int lenn) { lg[ls(p)]+=lg[p]; lg[rs(p)]+=lg[p]; sum[ls(p)]+=lg[p]*(lenn-(lenn>>1)); sum[rs(p)]+=lg[p]*(lenn>>1); lg[p]=0; } void update(int p,int l,int r,int nl,int nr,int k) { if (nl<=l&&r<=nr) { lg[p]+=k; sum[p]+=k*(r-l+1); return; } int mid=(l+r)>>1; push_down(p,(r-l+1)); if (nl<=mid) update(ls(p),l,mid,nl,nr,k); if (nr>mid) update(rs(p),mid+1,r,nl,nr,k); push_up(p); } void del(int p,int l,int r,int pos) { if (l==r&&r==pos) {sum[p]--;return;} int mid=(l+r)>>1; if (pos<=mid) del(ls(p),l,mid,pos); if (pos>mid) del(rs(p),mid+1,r,pos); } void query(int p,int l,int r,int xl,int xr) { if (xl<=l&&r<=xr) { res+=sum[p]; return; } push_down(p,(r-l+1)); int mid=(l+r)>>1; if (xl<=mid) query(ls(p),l,mid,xl,xr); if (xr>mid) query(rs(p),mid+1,r,xl,xr); } void dfs1(int x,int f,int deep) { dep[x]=deep; fa[x]=f; size[x]=1; int maxson=-1; for (int i=head[x];i;i=e[i].nx) { int y=e[i].to; if (y==fa[x]) continue; dfs1(y,x,deep+1); size[x]+=size[y]; if (size[y]>maxson) {son[x]=y;maxson=size[y];} } } void dfs2(int x,int topf) { id[x]=++tot; vt[tot]=v[x]; top[x]=topf; if (!son[x]) return; dfs2(son[x],topf); for (int i=head[x];i;i=e[i].nx) { int y=e[i].to; if (y==fa[x]||y==son[x]) continue; dfs2(y,y); } } void uprange(int x,int y) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); update(1,1,n,id[top[x]],id[x],1); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); update(1,1,n,id[x],id[y],1); } int main() { n=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i<n;i++) { int x,y; x=read();y=read(); add_edge(x,y); } root=a[1]; dfs1(root,0,1); dfs2(root,root); build(1,1,n); for (int i=1;i<=n-1;i++) { uprange(a[i],a[i+1]); } for (int i=2;i<=n;i++) update(1,1,n,id[a[i]],id[a[i]],-1); for (int i=1;i<=n;i++) { res=0; query(1,1,n,id[i],id[i]); printf("%d ",res); } return 0; }