10pts AC#5

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int t[600001];
int x,y;
int type;
int ans=0;
int cnt=0;
int vis[2000001];
int f[2000001];
int w[2000001];
int ori_w[2000001];
int id[2000001];
int maxson[2000001];
int res=0;
int top[2000001];
int lazy[2000001];
int dep[2000001];
int siz[2000001];
int d[2000001];
vector<int>q[2000001];
void build(int l,int r,int p){
    if(l==r){
        d[p]=w[l];
        vis[l]=p;
        return;
    }
    else
    {
        int mid=(l+r)/2;
        build(l,mid,2*p);
        build(mid+1,r,2*p+1);
        d[p]=d[2*p]+d[2*p+1];
    }
}
void update(int l,int r,int s,int t,int c,int p)
{
    if(l>=s && r<=t){
        d[p]+=c*(r-l+1);
        lazy[p]+=c;
        return;
    }
    if(lazy[p]){
        int mid=(l+r)/2;
        d[2*p]+=lazy[p]*(mid-l+1);
        d[2*p+1]+=lazy[p]*(r-mid);
        lazy[2*p]+=lazy[p];
        lazy[2*p+1]+=lazy[p];
        lazy[p]=0;
    }
    int mid=(l+r)/2;
    if(s<=mid){
        update(l,mid,s,t,c,2*p);
    }
    if(t>mid){
        update(mid+1,r,s,t,c,2*p+1);
    }
    d[p]=d[2*p]+d[2*p+1];
}
void change(int x,int y,int z)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap (x,y);
        update(1,n,id[top[x]],id[x],z,1);
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    update(1,n,id[x],id[y],z,1);
}
void dfs1(int x,int fa,int deep) 
{
    dep[x]=deep+1;
    f[x]=fa;
    siz[x]=1;
    int maxn=-1;
    for(int i=0;i<q[x].size();i++){
        int po=q[x][i];
        if(po==f[x])continue;
        dfs1(po,x,deep+1);
        siz[x]+=siz[po];
        if(siz[po]>maxn)maxn=siz[po],maxson[x]=po;
    }
}
void dfs2(int x,int topf) 
{
    id[x]=++cnt;
    w[cnt]=ori_w[x];
    top[x]=topf;
    if(!maxson[x])return;
    dfs2(maxson[x],topf);
    for(int i=0;i<q[x].size();i++){
        int po=q[x][i];
        if(po==f[x] || po==maxson[x])continue;
        dfs2(po,po);
    }
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>t[i];
    for(int i=1;i<=n-1;i++){
        cin>>x>>y;
        q[x].push_back(y);
        q[y].push_back(x);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,n,1);
    int ans=0;
    for(int i=2;i<=n;i++){
        change(t[i-1],t[i],1);
    }
    for(int i=2;i<=n;i++){
        d[vis[id[t[i]]]]--;
    }
    for(int i=1;i<=n;i++){
        cout<<d[vis[id[i]]]<<endl;
    }
}