树上路径计数

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有一棵包含 $n$ 个顶点的树，树边按照输入顺序编号为 $1$ 到 $n-1$。

给定 $k$ 次旅行。每次旅行从一个顶点出发，沿树上的唯一简单路径走到另一个顶点。

请按输入顺序统计每条边被这 $k$ 次旅行经过了多少次。

输入格式

第一行包含一个整数 $n$。

接下来 $n-1$ 行，每行包含两个整数 $x,y$，表示顶点 $x$ 与顶点 $y$ 之间有一条边。

接下来一行包含一个整数 $k$。

接下来 $k$ 行，每行包含两个整数 $x,y$，表示一次从顶点 $x$ 到顶点 $y$ 的旅行。

输出格式

输出一行 $n-1$ 个整数。第 $i$ 个整数表示输入中的第 $i$ 条边被经过的次数。

样例输入 1

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

样例输出 1

2 1 1 1

样例输入 2

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

样例输出 2

3 1 1 1

数据范围

对于所有测试数据，$2\le n\le 10^5$，$0\le k\le 10^5$，边的两个端点和每次旅行的两个端点均在 $[1,n]$ 内；输入的 $n-1$ 条边构成一棵树。