P17268 [ICPC 2017 Urumqi R] Lowest Common

In graph theory the lowest common ancestor $(LCA)$ of two nodes $v$ and $w$ in a rooted tree $T$ is the deepest node that has both $v$ and $w$ as descendants. Here we define each node to be a descendant of itself. The LCA of two nodes in $T$ is the shared ancestor of them that is located farthest from the root. But how about an un-rooted tree? In this problem you are given an un-rooted tree $T$ with $n$ nodes labelled from $1$ to $n$ and several pairs of nodes $(v_i, w_i)$. For each node $x$ of $T$, consider the tree rooted by $x$ which becomes a rooted tree; and calculate the summation $\sum_{i} LCA(v_i, w_i)$.

The input has several test cases and the first line contains an integer $t (1 \le t \le 28)$ which is the number of test cases. For each test case, the first line contains two integers $n$ and $q (1 \le n, q \le 100000)$. Each of the following $n - 1$ lines describes an edge with two integers $v$ and $w (1 \le v, w \le n)$. Then following $q$ lines contain $q$ pairs of nodes $(v_i, w_i)$ described as above $(1 \le v_i, w_i \le n)$. Both of the sum of $n$ and the sum of $q$ in input are smaller than $1000000$.

For each test case, output a line with $n$ integers. The $i$-th one is the value of $\sum_{i} LCA(v_i, w_i)$ corresponding to the tree rooted by the $i$-th node.