{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e在\u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME60/mandarin/TSUM2.pdf\"\u003e普通话\u003c/a\u003e和\u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME60/vietnamese/TSUM2.pdf\"\u003e越南语\u003c/a\u003e中阅读问题陈述。\u003c/h3\u003e\n\n给定一棵有$N$个节点(编号为$1$到$N$)和$N-1$条边的树。每个节点都有一个值;我们用$W_x$表示节点$x$的值。\n\n接下来,让我们定义树中简单路径$v_1, v_2, \\dots, v_k$的值为$\\sum_{i\u003d1}^k i \\cdot W_{v_i}$。树中的简单路径是一系列节点$v_1, v_2, \\dots, v_k$的序列,满足以下条件:\n- $k \\ge 1$\n- 对于每个$i$($1 \\le i \\le k-1$),节点$v_i$和$v_{i+1}$之间有一条边\n- 对于每个$i, j$($1 \\le i, j \\le k$),满足$i \\neq j$\n\n你需要找出给定树中所有简单路径的最大值。\n\n### 输入\n- 输入的第一行包含一个整数$T$,表示测试用例的数量。接下来是$T$个测试用例的描述。\n- 每个测试用例的第一行包含一个整数$N$。\n- 第二行包含$N$个空格分隔的整数$W_1, W_2, \\dots, W_N$。\n- 接下来的$N-1$行,每行包含两个用空格分隔的整数$u$和$v$,表示节点$u$和$v$之间有一条边。\n\n### 输出\n对于每个测试用例,输出一行,包含一个整数 — 简单路径的最大值。\n\n### 约束条件\n- $2 \\le N \\le 50,000$\n- 所有测试用例中$N$的总和不超过$400,000$\n- $1 \\le u, v \\le N$\n- $u \\neq v$\n- 对于每个有效的$i$,满足$|W_i| \\le 1,000$\n- 输入中描述的图是一棵树\n\n### 子任务\n**子任务 #1 (30 分):** 树是以节点1为根的二叉树\n\n**子任务 #2 (30 分):**\n- 树中任意简单路径的长度(节点数)最多为$200$\n- 所有测试用例中$N$的总和不超过$100,000$\n\n**子任务 #3 (40 分):** 原始约束条件"}},{"title":"示例 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n5\r\n1 2 3 4 5\r\n1 2\r\n2 3\r\n3 4\r\n3 5\r\n2\r\n-1 -1\r\n1 2\r\n3\r\n1 1000 -30\r\n1 3\r\n2 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e34\r\n-1\r\n2941\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}