路径经过的点数统计

难度：T4

【知识点：树上差分】

前置知识：树上差分及其冻结前置单元。

题目描述与输入

第一行$n$ $m$，随后$m$行树边$u$ $v$ $w$（忽略$w$）；再读$q$，随后$q$行$u$ $v$代表一次路径通行。求每个顶点被经过的次数，包含两端。

输出

按顶点编号输出$n$个计数。

数据范围

$1 \le n \le 80$，$m=n - 1$，$1 \le q \le 200$；每条查询贡献$1$次，$w$忽略。

样例输入

5 4
1 2 2
2 3 3
2 4 1
4 5 4
4
3 5
2 2
1 5
4 5

样例输出

1 3 1 3 3

样例说明

通行路径包含两端；第二次$2$→$2$只给点$2$增加一次。逐点累加得到$1$、$3$、$1$、$3$、$3$。