题目大意：n个城市有n-1条道路相连（一棵树），有m条公交线路（都是两个城市之间的最短路），请问每条道路上分别有多少条公交线路？

输入

输出

样例输入

7 3
1 1 2 3 3 3
4 5
5 7
1 6

样例输出

2 1 1
3 1 2
4 2 1
5 3 2
6 3 1
7 3 1

提示

解题思路

差分可以让区间修改转化成单点修改，如城市a和城市b有一条公交线路，a和b的公共祖先的c，那么我们可以在点a标记+1（根结点到a所有路径都+1），在点c标记-1（根结点到c所有路径都-1），这样就相当于a到c之间的路径全部+1，因为c以上的由于+1和-1抵消，并没有增加公交线路（b到c之间也是如此）。打完标记后，自下而上把儿子结点的标记累加到父亲结点，这样每个结点到其父亲结点道路上的公交线路就统计出来了。

程序实现

树链剖分求LCA代码：