题目：
松鼠的新家是一棵树，前几天刚刚装修好了新家，新家有 个房间，并且有 根树枝连接，每个房间都可以相互到达，且任两个房间之间的路线都是唯一的。天哪，他居然真的住在「树」上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去 ，再去 ，……，最后到 ，来参观新家。
可是这样会导致维尼重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。维尼是个馋家伙，立马就答应了。
现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间 是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。
样例输入：
5
1 4 5 3 2
1 2
2 4
2 3
4 5
样例输出：
1
2
1
2
1
题解：
大思路：
读完题我们不难发现：假设路径为a[1]–>a[2]–>a[3]–>…–>a[n]，若要从a[i]到a[j]那么在它走过的路径上我们要放一颗糖，因为要最少所以不难想到走最短的路，那么就是走a[i]->lca(a[i], a[j])->a[j]，然后再将这段路每一个点加上1。
细节：
那么如何将a[i]->lca(a[i], a[j])->a[j]这段路每一个点加上1呢，这需要用到我们的“树上点差分”：如图若要求U->lca(U, V)->V这段路所有点加1，则首先我们要将U，V点加1，然后再将lca和lca的父节点减1，最后如果要求某一结点的值那么则将它的子树（包括他自己）加起来求和，最后和即为答案。 为什么是这样呢？ 如图若我们将某一结点加1，再对它的父节点求子树和,那么所有的父节点都会有影响，但是我们的目的是让U->lca(U, V)->V这段路所有点加1，所以就要将多余的剪掉：首先lca这个点要减1，因为求子数和的话它会是2，但实际上他是1，然后就是lca的父节点，不难看到它和我们这条路段没有关系，但是却加了个1，所以同样将他减1，这样操作后就只有这段路被加了1，其他节点并未影响。 （感觉与写普通差分方法很类似） 这样算出来我们会发现1以后的节点被多算了1，这是因为在求差分数组时我们将后面的节点既作为起点又作为终点算了两遍，所以要剔除。
for(int i
= 2;i
<= n
; i
++) ans
[a
[i
]]--;
代码：
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std
;
const int MAXN
= 300005;
int n
, v
[MAXN
* 2], head
[MAXN
], _next
[MAXN
* 2], tot
, d
[MAXN
], fa
[MAXN
][55], lu
, q
, chafen
[MAXN
];
queue
<int> qu
;
int ans
[MAXN
], a
[MAXN
];
void add(int x
, int y
) {
v
[++tot
] = y
;
_next
[tot
] = head
[x
];
head
[x
] = tot
;
}
void bfs() {
d
[1] = 1;
qu
.push(1);
while (!qu
.empty()) {
int qi
= qu
.front();
qu
.pop();
for (int i
= head
[qi
]; i
; i
= _next
[i
]) {
int son
= v
[i
];
if (d
[son
])
continue;
d
[son
] = d
[qi
] + 1;
fa
[son
][0] = qi
;
for (int j
= 1; j
<= lu
; j
++) fa
[son
][j
] = fa
[fa
[son
][j
- 1]][j
- 1];
qu
.push(son
);
}
}
}
int LCA(int a
, int b
) {
fa
[1][0] = 1;
if (d
[a
] > d
[b
])
swap(a
, b
);
for (int i
= lu
; i
>= 0; i
--) {
if (d
[fa
[b
][i
]] >= d
[a
]) {
b
= fa
[b
][i
];
}
}
if (a
== b
)
return a
;
for (int i
= lu
; i
>= 0; i
--) {
if (fa
[b
][i
] != fa
[a
][i
]) {
a
= fa
[a
][i
];
b
= fa
[b
][i
];
}
}
return fa
[a
][0];
}
void dfs(int x
, int father
) {
for(int i
= head
[x
];i
;i
= _next
[i
]) {
int y
= v
[i
];
if(y
!= father
) {
dfs(y
, x
);
chafen
[x
] += chafen
[y
];
}
}
}
int main() {
scanf("%d", &n
);
int x
, y
;
for(int i
= 1;i
<= n
; i
++) scanf("%d", &a
[i
]);
for (int i
= 1; i
<= n
- 1; i
++) {
scanf("%d %d", &x
, &y
);
add(x
, y
);
add(y
, x
);
}
lu
= (int)(log(n
) / log(2)) + 1;
bfs();
for(int i
= 2;i
<= n
; i
++) {
int lca
= LCA(a
[i
], a
[i
- 1]);
chafen
[lca
]--;
chafen
[a
[i
]]++;
chafen
[a
[i
- 1]]++;
if(lca
!= 1) chafen
[fa
[lca
][0]]--;
}
dfs(1, -1);
for(int i
= 1; i
<= n
; i
++) {
if(i
!= a
[1]) printf("%d\n", chafen
[i
] - 1);
else printf("%d\n", chafen
[i
]);
}
return 0;
}
