傻瓜与道路(Fools and Roads)

题目描述

有一颗 $n$ 个节点的树，$k$ 次旅行，问每一条边被走过的次数。

输入格式

第一行一个整数 $n$ （$2\leq n\leq 10^5$ ）。

接下来 $n-1$ 行，每行两个正整数 $x,y$ （$1\leq x,y\leq n,x\neq y$ ），表示 $x$ 与 $y$ 之间有一条连边。

接下来一个整数 $k$ （$0\leq k\leq 10^5$ ）。

接下来 $k$ 行，每行两个正整数 $x,y$ （$1\leq x,y\leq n$ ），表示有一个从 $x$ 到 $y$ 的旅行。

输出格式

一行空格分隔的 $n - 1$ 个整数，按输入顺序输出每一条边被走过的次数。

Translated by @larryzhong

样例输入 #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

数据范围

In the first sample the fool number one goes on the first and third road and the fool number $3$ goes on the second, first and fourth ones.

In the second sample, the fools number $1$, $3$ and $5$ go on the first road, the fool number $5$ will go on the second road, on the third road goes the fool number $3$, and on the fourth one goes fool number $1$.

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接