题目背景

小珅和小泽在郊外发现了一棵神奇的魔法树，树上一共有$n$ 个魔法节点，每个节点都镶嵌着一枚带有专属权值的魔法晶石。

经过研究，两人发现了这棵树的特殊规律：距离恰好为$2$的两个魔法节点可以产生联动效果，迸发联合魔力。两个节点的晶石权值相乘，就是这组节点的联合权值。

为了收集魔法能量，小珅和小泽想要统计这棵魔法树上的关键数据：找出所有合法节点对中最大的联合权值，同时算出所有联合权值的总和，用来解锁魔法树的隐藏力量。

题目描述

给定一棵包含 $n$ 个节点的树，每个节点拥有一个正整数权值。

若两个节点 $u,v$ 的距离为 $2$，则称这两个节点为一组联合点对，其联合权值为两节点权值的乘积。

请你帮助小珅和小泽求出：

1. 树上所有联合点对的最大联合权值；
2. 树上所有不同联合点对的联合权值总和，结果对 $10007$ 取模。

输入格式

第一行一个整数 $n$，表示树的节点个数。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示树上有一条连接节点 $u$ 和节点 $v$ 的无向边。

最后一行 $n$ 个整数 $w_1,w_2,\dots,w_n$，其中 $w_i$ 表示第 $i$ 个节点的晶石权值。

输出格式

输出一行两个整数，依次为最大联合权值、联合权值总和（总和对 $10007$ 取模）。

输入输出样例

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

20 74

说明/提示

样例解释

树上距离为 $2$ 的合法无序联合点对共四组：$(1,3),(1,4),(2,5),(3,4)$。 对应联合权值分别为：$1 \times 2=2$、$1 \times 3=3$、$5 \times 10=50$、$2 \times 3=6$。 其中最大联合权值为 $50$，所有权值累加总和为 $2+3+50+6=74$

数据说明

• 对于 $30\%$ 的数据，$2 < n \leq 100$；
• 对于 $60\%$ 的数据，$2 < n \leq 2000$；
• 对于 $100\%$ 的数据，$2 < n \leq 2\times 10^5$，$0 < W_i \leq 10000$。

保证一定存在可产生联合权值的有序点对。

12
1 2
2 3
2 4
2 5
4 6
6 7
1 8
3 9
4 10
1 11
1 12
467 837 412 998 837 910 873 627 660 321 680 784

871254 4070

16
1 2
1 3
3 4
2 5
1 6
6 7
2 8
4 9
3 10
1 11
4 12
9 13
9 14
3 15
11 16
346 934 900 389 740 227 111 45 105 314 754 844 519 120 235 44

840600 2802