7626: [CSES Problem Set] Counting Paths
[Creator : ]
Description
You are given a tree consisting of $n$ nodes, and $m$ paths in the tree.
Your task is to calculate for each node the number of paths containing that node.
Your task is to calculate for each node the number of paths containing that node.
Input
The first input line contains integers $n$ and $m$: the number of nodes and paths. The nodes are numbered $1,2,\ldots,n$.
Then there are $n-1$ lines describing the edges. Each line contains two integers $a$ and $b$: there is an edge between nodes $a$ and $b$.
Finally, there are $m$ lines describing the paths. Each line contains two integers $a$ and $b$: there is a path between nodes $a$ and $b$.
Then there are $n-1$ lines describing the edges. Each line contains two integers $a$ and $b$: there is an edge between nodes $a$ and $b$.
Finally, there are $m$ lines describing the paths. Each line contains two integers $a$ and $b$: there is a path between nodes $a$ and $b$.
Output
Print $n$ integers: for each node $1,2,\ldots,n$, the number of paths containing that node.
Constraints
$1≤n,m≤2⋅10^5$
$1 \le a,b \le n$
$1 \le a,b \le n$
Sample 1 Input
5 3
1 2
1 3
3 4
3 5
1 3
2 5
1 4
Sample 1 Output
3 1 3 1 1