Description

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?

Input Format

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 Format

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$.

5  
1 2  
2 3
3 4  
4 5  
1 5 2 3 10 

20 74

Hint

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