https://www.luogu.org/problemnew/show/P3258
注意开始和最后结尾
#include <bits/stdc++.h>
#define read read()
#define up(i,l,r) for(register int i = (l);i <= (r);i++)
#define down(i,l,r) for(register int i = (l);i >= (r);i--)
#define traversal_vedge(i) for(register int i = head[u]; i ;i = e[i].nxt)
#define ll long long
using namespace std;
int read
{
int x = , f = ; char ch = getchar();
while(ch < || ch > ) {if(ch == '-')f = -; ch = getchar();}
while(ch >= && ch <=) {x = * x + ch - ;ch = getchar();}
return x * f;
}
//--------------------------------------------------------------------
const int N = ;
int n,a[N];
struct edge{
int v,nxt;
}e[N<<]; int tot,head[N];
void add(int u,int v) {e[++tot] = (edge){v,head[u]};head[u] = tot;} int dep[N],size[N],fa[N],top[N];
int cnt[N]; void dfs(int u)
{
dep[u] = dep[fa[u]]+;
size[u] = ;
top[u] = u;
int hson_id = ,hson_size = ;
traversal_vedge(i)
{
int v = e[i].v;
if(v == fa[u]) continue;
fa[v] = u;
dfs(v);
size[u] += size[v];
if(size[v] > hson_size) hson_id = v,hson_size = size[v];
}
if(hson_id) top[hson_id] = u;
} int find(int u)
{
if(top[u] == u) return u;
top[u] = find(top[u]);
return top[u];
} int lca(int x,int y)
{
if(find(x) != find(y))
{
if(dep[top[x]] > dep[top[y]]) return lca(fa[top[x]],y);
else return lca(x,fa[top[y]]);
}
return dep[x] > dep[y] ? y : x;
} void dfs_tree(int u)
{
traversal_vedge(i)
{
int v = e[i].v;
if(v == fa[u]) continue;
dfs_tree(v);
cnt[u] += cnt[v];
}
} void readdata()
{
n = read;
up(i,,n) a[i] = read;
up(i,,n-)
{
int u = read, v = read;
add(u,v);
add(v,u);
}
dfs();
up(i,,n-)
{
int u = a[i], v = a[i+];
//cnt[u]++;
cnt[fa[u]]++;
cnt[v]++;
int LCA = lca(u,v);
cnt[LCA]--; cnt[fa[LCA]]--;
}
dfs_tree();
up(i,,n)
{
if(i == a[]) cnt[i]++;
else if(i == a[n]) cnt[i]--;
printf("%d\n",cnt[i]);
}
} int main()
{
readdata();
return ;
}