P1351 [NOIP 2014 Senior] Joint Weight

NOIP 2014 Senior D1T2.

An undirected connected graph $G$ has $n$ vertices and $n-1$ edges. The vertices are numbered from $1$ to $n$, and the weight of vertex $i$ is $W_i$. Each edge has length $1$. For any two vertices $u$ and $v$, their distance is defined as the length of the shortest path from $u$ to $v$. For a pair of vertices $(u, v)$ in $G$, if their distance is $2$, then they generate a joint weight of $W_v \times W_u$. Among all ordered pairs in $G$ that can generate a joint weight, what is the maximum joint weight? What is the sum of all joint weights?

The first line contains $1$ integer $n$. The next $n-1$ lines each contain $2$ positive integers $u, v$ separated by a space, indicating that there is an edge between vertex $u$ and vertex $v$. The last line contains $n$ positive integers separated by single spaces, where the $i$-th integer indicates that the weight of vertex $i$ in $G$ is $W_i$.

Output a single line containing $2$ integers separated by a space: the maximum joint weight on graph $G$ and the sum of all joint weights. Since the sum may be large, output it modulo $10007$.

Sample Explanation.  For the input in this example, the graph is as shown above. The ordered pairs at distance $2$ are $(1, 3), (2, 4), (3, 1), (3, 5), (4, 2), (5, 3)$. Their joint weights are $2, 15, 2, 20, 15, 20$. The maximum is $20$, and the total sum is $74$. Constraints - For $30\%$ of the testdata, $2 < n \leq 100$. - For $60\%$ of the testdata, $2 < n \leq 2000$. - For $100\%$ of the testdata, $2 < n \leq 2 \times 10^5$, $0 < W_i \leq 10000$. It is guaranteed that there exists at least one ordered pair that can generate a joint weight. Translated by ChatGPT 5