{"trustable":true,"prependHtml":"\u003cstyle\u003e.table {width: 100%;} .table-bordered {border: 1px solid #222; border-collapse: collapse; border-spacing: 0;} .table-bordered th { border: 1px solid #222; }.table-bordered td { border: 1px solid #222; padding: 0 5px; }\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e无向连通图 $G$ 有 $n$ 个点,$n-1$ 条边。点从 $1$ 到 $n$ 依次编号,编号为 $i$ 的点的权值为 $W_i$,每条边的长度均为 $1$。图上两点 $(u, v)$ 的距离定义为 $u$ 点到 $v$ 点的最短距离。对于图 $G$ 上的点对 $(u, v)$,若它们的距离为 $2$,则它们之间会产生$W_v \\times W_u$ 的联合权值。\u003c/p\u003e\n\u003cp\u003e请问图 $G$ 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?\u003c/p\u003e\n\u003ch3\u003e输入格式\u003c/h3\u003e\n\u003cp\u003e第一行包含 $1$ 个整数 $n$。\u003c/p\u003e\n\u003cp\u003e接下来 $n-1$ 行,每行包含 $2$ 个用空格隔开的正整数 $u,v$,表示编号为 $u$ 和编号为 $v$ 的点之间有边相连。\u003c/p\u003e\n\u003cp\u003e最后 $1$ 行,包含 $n$ 个正整数,每两个正整数之间用一个空格隔开,其中第 $i$ 个整数表示图 $G$ 上编号为 $i$ 的点的权值为 $W_i$。\u003c/p\u003e\n\u003ch3\u003e输出格式\u003c/h3\u003e\n\u003cp\u003e输出共 $1$ 行,包含 $2$ 个整数,之间用一个空格隔开,依次为图 $G$ 上联合权值的最大值和所有联合权值之和。\u003cstrong\u003e由于所有联合权值之和可能很大,输出它时要对$10007$取余\u003c/strong\u003e。\u003c/p\u003e\n\u003ch3\u003e样例一\u003c/h3\u003e\n\u003ch4\u003einput\u003c/h4\u003e\n\u003cpre\u003e5\n1 2\n2 3\n3 4\n4 5\n1 5 2 3 10\n\n\u003c/pre\u003e\n\n\u003ch4\u003eoutput\u003c/h4\u003e\n\u003cpre\u003e20 74\n\n\u003c/pre\u003e\n\n\u003ch4\u003eexplanation\u003c/h4\u003e\n\u003cp\u003e距离为 2 的有序点对有$(1,3), (2,4), (3,1), (3,5), (4,2), (5,3)$。其联合权值分别为 $2, 15, 2, 20, 15, 20$。其中最大的是 $20$,总和为 $74$。\u003c/p\u003e\n\u003ch3\u003e限制与约定\u003c/h3\u003e\n\u003cp\u003e对于30%的数据,$1 \u0026lt; n \\leq 100$;\u003c/p\u003e\n\u003cp\u003e对于60%的数据,$1 \u0026lt; n \\leq 2000$;\u003c/p\u003e\n\u003cp\u003e对于100%的数据,$1 \u0026lt; n \\leq 200000, 0 \u0026lt; W_i \\leq 10000$。\u003c/p\u003e\n\u003cp\u003e保证一定存在可产生联合权值的有序点对。\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e时间限制:\u003c/strong\u003e$1\\texttt{s}$\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e内存限制:\u003c/strong\u003e$128\\texttt{MB}$\u003c/p\u003e\n\u003ch3\u003e下载\u003c/h3\u003e\n\u003cp\u003e\u003ca href\u003d\"https://uoj.ac/download.php?type\u003dproblem\u0026amp;id\u003d16\"\u003e样例数据下载\u003c/a\u003e\u003c/p\u003e\n"}}]}