链剖。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxv 300500
#define maxe 600500
using namespace std;
int n,a[maxv],x,y,nume=,g[maxv];
int w[maxv],fath[maxv],dis[maxv],son[maxv],size[maxv],top[maxv],tot=;
int ls[maxv<<],rs[maxv<<],lazy[maxv<<],root,cnt=,ans[maxv];
struct edge
{
int v,nxt;
}e[maxe];
void addedge(int u,int v)
{
e[++nume].v=v;
e[nume].nxt=g[u];
g[u]=nume;
}
void dfs1(int x)
{
size[x]=;son[x]=;
for (int i=g[x];i;i=e[i].nxt)
{
int v=e[i].v;
if (v!=fath[x])
{
fath[v]=x;
dis[v]=dis[x]+;
dfs1(v);
size[x]+=size[v];
if (size[v]>size[son[x]])
son[x]=v;
}
}
}
void dfs2(int x,int father)
{
top[x]=father;w[x]=++tot;
if (son[x]) dfs2(son[x],father);
for (int i=g[x];i;i=e[i].nxt)
{
int v=e[i].v;
if ((v!=fath[x]) && (v!=son[x]))
dfs2(v,v);
}
}
void build(int &now,int left,int right)
{
now=++cnt;lazy[now]=;
if (left==right) return;
int mid=(left+right)>>;
build(ls[now],left,mid);
build(rs[now],mid+,right);
}
void modify(int now,int left,int right,int l,int r)
{
if ((left==l) && (right==r))
{
lazy[now]++;
return;
}
int mid=(left+right)>>;
if (r<=mid) modify(ls[now],left,mid,l,r);
else if (l>=mid+) modify(rs[now],mid+,right,l,r);
else
{
modify(ls[now],left,mid,l,mid);
modify(rs[now],mid+,right,mid+,r);
}
}
void work(int x)
{
int p,q,f1,f2;
p=a[x];q=a[x+];
f1=top[p];f2=top[q];
while (f1!=f2)
{
if (dis[f1]<dis[f2])
{
swap(p,q);
swap(f1,f2);
}
modify(root,,n,w[f1],w[p]);
p=fath[f1];f1=top[p];
}
if (dis[p]>dis[q]) swap(p,q);
modify(root,,n,w[p],w[q]);
}
int ask(int now,int left,int right,int p)
{
if ((left==right) && (left==p))
return lazy[now];
int mid=(left+right)>>;
if (p<=mid) return ask(ls[now],left,mid,p)+lazy[now];
else return ask(rs[now],mid+,right,p)+lazy[now];
}
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%d",&a[i]);
for (int i=;i<=n-;i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
dfs1();
dfs2(,);
build(root,,n);
for (int i=;i<=n-;i++)
work(i);
for (int i=;i<=n;i++)
{
int now=ask(root,,n,w[a[i]]);
if (i!=) now--;
ans[a[i]]=now;
}
for (int i=;i<=n;i++)
printf("%d\n",ans[i]);
return ;
}