Description
松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请****前来参观，并且还指定一份参观指南，他希望**能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。
可是这样会导致**重复走很多房间，懒惰的**不听地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。**是个馋家伙，立马就答应了。
现在松鼠希望知道为了保证**有糖果吃，他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当**在参观的最后到达餐厅时就不需要再拿糖果吃了。
Input
第一行一个整数n，表示房间个数
第二行n个整数，依次描述a1-an
接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。
Output
一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让**有糖果吃。
Sample Input
5
1 4 5 3 2
1 2
2 4
2 3
4 5
1 4 5 3 2
1 2
2 4
2 3
4 5
Sample Output
1
2
1
2
1
2
1
2
1
HINT
2<= n <=300000
非常裸的树上差分。
注意最后把算了两遍的减1
#include <iostream> #include <cstdio> #include <queue> #include <cstdlib> using namespace std; #define reg register inline int read() { int res = 0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48), ch=getchar(); return res; } #define N 300005 int n; struct edge { int nxt, to; }ed[N*2]; int head[N], cnt; inline void add(int x, int y) { ed[++cnt] = (edge){head[x], y}; head[x] = cnt; } int a[N]; bool vis[N]; int dep[N]; int f[N][20]; inline void bfs() { dep[0] = -1; dep[1] = 1; queue <int> q; q.push(1); while(!q.empty()) { int x = q.front();q.pop(); for (reg int i = head[x] ; i ; i = ed[i].nxt) { int to = ed[i].to; if (dep[to]) continue; dep[to] = dep[x] + 1; q.push(to); f[to][0] = x; for (reg int j = 1 ; j <= 19 ; j ++) f[to][j] = f[f[to][j-1]][j-1]; } } } inline int lca(int x, int y) { if (dep[x] < dep[y]) swap(x, y); for (reg int i = 19 ; i >= 0 ; i --) if (dep[f[x][i]] >= dep[y]) x = f[x][i]; if (x == y) return x; for (reg int i = 19 ; i >= 0 ; i --) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i]; return f[x][0]; } int cf[N], ans[N]; void dfs(int x) { ans[x] = cf[x]; for (reg int i = head[x] ; i ; i = ed[i].nxt) { int to = ed[i].to; if (to == f[x][0]) continue; dfs(to); ans[x] += ans[to]; } } int main() { n = read(); for (reg int i = 1 ; i <= n ; i ++) a[i] = read(); for (reg int i = 1 ; i < n ; i ++) { int x = read(), y = read(); add(x, y), add(y, x); } bfs(); for (reg int i = 1 ; i <= n - 1 ; i ++) { int x = a[i], y = a[i+1]; int l = lca(x, y); cf[x]++, cf[y]++; cf[l]--, cf[f[l][0]]--; } dfs(1); for (reg int i = 2 ; i <= n ; i ++) ans[a[i]]--; for (reg int i = 1 ; i <= n ; i ++) printf("%d ", ans[i]); return 0; }