rt,求调，奖励关注

#include<bits/stdc++.h>
using namespace std;
int fa[1000001],son[1000001],to[1000001],idx[1000001],nxt[1000001],cnt,fir[1000001],sz[1000001],seq[1000001],tmr,dfn[1000001],t[1000001],n;
#define lowbit(x) ((x)&(-x))
int a[1000001],top[1000001],depth[1000001];
void add(int x,int y)
{
    to[++cnt]=x;nxt[cnt]=fir[y];fir[y]=cnt;
    to[++cnt]=y;nxt[cnt]=fir[x];fir[x]=cnt;
}
void dfs1(int x,int f)
{
    depth[x]=depth[fa[x]=f]+(sz[x]=1);
    for(int i=fir[x];i;i=nxt[x])
    {
        int v;
        if((v=to[i])!=f)
        {
            dfs1(v,x);
            sz[x]+=sz[v];
            if(sz[v]>sz[son[x]])son[x]=v;
        }
    }
}
void dfs2(int x,int f)
{
    top[x]=f;
    seq[dfn[x]=++tmr]=x;
    if(son[x])dfs2(son[x],f);
    for(int i=fir[x];i;i=nxt[x])
    {
        int v;
        if((v=to[i])!=fa[x]&&v!=son[x])
        {
            dfs2(v,v);
        }
    }
}
void update(int x,int f)
{
    while(x<=n)
    {
        t[x]+=f;
        x += x&-x;
    }
}
int getsum(int x) 
{
    int res=0;
    while(x) 
    {
        res+=t[x];
        x-=x&-x;
    } 
    return res;
}
void modify(int x,int y,int z)
{ 
    update(x,z);
    update(y+1,-z); 
}
void query(int u,int v) 
{
    while(top[u]^top[v])
    {
        if(depth[top[u]]<depth[top[v]])swap(u,v);
        modify(dfn[top[u]],dfn[u],1);
        u=fa[top[u]];
    }
    if(depth[u]<depth[v])swap(u, v);
    modify(dfn[v],dfn[u],1);
}
int main () 
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
    {
       int x,y;
       scanf("%d%d",&x,&y);
       add(x,y);        
    }
    dfs1(1,0),dfs2(1,1);
    for(int i=2;i<=n;i++) 
    {
        query(a[i],a[i-1]);
        update(dfn[a[i]],-1);
        update(dfn[a[i]]+1,1);
    }
    for(int i=1;i<=n;i++)printf("%d\n",getsum(dfn[i]));
}

https://www.luogu.com.cn/problem/P3258