Description
松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。
可是这样会导致维尼重复走很多房间，懒惰的维尼不听地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。维尼是个馋家伙，立马就答应了。
现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。
Input
第一行一个整数n，表示房间个数
第二行n个整数，依次描述a1-an
接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。
Output
一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。
题解：
树剖 + 线段树显然是可以的.
不过可以用更加简单的树上查分.
对于 $<u,c,v>$ ($c$ 为 $lca(u,v)$)
只需对于 $u,v$ 加上差值， $c$ 与 $fa[c]$上减掉差值即可.
注意：每次要将除了 $1$ 以外其他所有点的点权都减 1.
因为上述方法会把中转点算两次
不过可以用更加简单的树上查分.
对于 $<u,c,v>$ ($c$ 为 $lca(u,v)$)
只需对于 $u,v$ 加上差值， $c$ 与 $fa[c]$上减掉差值即可.
注意：每次要将除了 $1$ 以外其他所有点的点权都减 1.
因为上述方法会把中转点算两次
Code:
#include<bits/stdc++.h>
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 300001
using namespace std;
int hd[maxn], to[maxn<<1], nex[maxn<<1], fa[maxn], siz[maxn], top[maxn], hson[maxn],len[maxn],arr[maxn],buck[maxn];
int edges;
int ans[maxn];
void add(int u,int v)
{
nex[++edges]=hd[u], hd[u]=edges, to[edges]=v;
}
void dfs1(int u,int ff)
{
fa[u] = ff, siz[u] = 1, len[u] = len[ff] + 1;
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(v==ff) continue;
dfs1(v,u);
siz[u] += siz[v];
if(siz[v] > siz[hson[u]]) hson[u] = v;
}
}
void dfs2(int u,int tp)
{
top[u]=tp;
if(hson[u]) dfs2(hson[u], tp);
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(v==fa[u] || v==hson[u]) continue;
dfs2(v, v);
}
}
int lca(int a,int b)
{
while(top[a] ^ top[b]) len[top[a]] < len[top[b]] ? b = fa[top[b]] : a = fa[top[a]];
return len[a] > len[b] ? b : a;
}
void dfs(int u)
{
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
if(v==fa[u]) continue;
dfs(v);
buck[u]+=buck[v];
}
}
int main()
{
// setIO("input");
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&arr[i]);
for(int i=1;i<n;++i)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v), add(v,u);
}
dfs1(1,0);
dfs2(1,1);
for(int i=2;i<=n;++i)
{
int c = lca(arr[i], arr[i-1]);
++buck[arr[i]];
++buck[arr[i-1]];
--buck[c];
--buck[fa[c]];
}
dfs(1);
for(int i=2;i<=n;++i) --buck[arr[i]];
for(int i=1;i<=n;++i)
{
printf("%d\n",buck[i]);
}
return 0;
}