P16219 [ECUSTPC 2025] Forest Path

Maddy got lost in the forest..., and she saw a strange tree. In front of her is a tree of size $n$, which is an undirected, acyclic, connected graph $T$ with $n$ vertices and $n-1$ edges. However, when Maddy was not paying attention, the shape of the tree changed: a newly grown branch connected two different non-adjacent vertices! That is, the tree $T$ became an undirected connected graph $G'$ with $n$ vertices and $n$ edges. To test you, Maddy gives the original shape of the tree and the values $\sum D_i$ for all vertices, where $\sum D_i$ is the sum of distances from vertex $i$ to every other vertex in the new graph $G'$, i.e., $\sum D_i = \sum_{j \in V} D_{G'}(i, j)$. You need to tell Maddy which two vertices are connected by the newly grown branch.

The first line contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases. For each test case, the first line contains an integer $n$ ($3 \le n \le 10^5$), indicating the number of vertices in the graph. Then follow $n-1$ lines, each containing two integers $u$ and $v$ ($1 \le u, v \le n, u \ne v$), indicating that there is an edge between $u$ and $v$ in the tree $T$. Then one line contains $n$ integers $\sum D_1, \sum D_2, \dots, \sum D_n$, representing for each vertex the sum of distances to all other vertices in $G'$. It is guaranteed that across all test cases, $\sum n \le 3 \times 10^5$. Also, in each test case the input graph forms a tree, and the two endpoints of the hidden edge are distinct and non-adjacent in the original graph.

For each test case, output one line with two integers $x$ and $y$, indicating the two vertices connected by the newly grown branch. If there are multiple valid answers, you may output any one of them. (For example, if $1\ 2$ is valid, then $2\ 1$ is also valid.)

### Explanation for Sample 1 The following figure shows the shape of $G'$. :::align{center}  ::: ### Hint The distance $D_{i,j}$ in the graph is defined as the minimum number of edges among all paths starting from $i$ and ending at $j$. Translated by ChatGPT 5