{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003eRead problems statements in \u003ca target\u003d\"_blank\" \r\nhref\u003d\"https://www.codechef.com/download/translated/LTIME60/mandarin/TSUM2.pdf\"\u003eMandarin chinese\u003c/a\u003e and \u003ca target\u003d\"_blank\" \r\nhref\u003d\"https://www.codechef.com/download/translated/LTIME60/vietnamese/TSUM2.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\r\n\r\nYou are given a tree with $N$ nodes (numbered $1$ through $N$) and $N-1$ edges. Each node has a value; let\u0027s denote the value of node $x$ by $W_x$.\r\n\r\nNext, let\u0027s define the value of a simple path $v_1, v_2, \\dots, v_k$ as $\\sum_{i\u003d1}^k i \\cdot W_{v_i}$. A simple path in a tree is a sequence of nodes $v_1, v_2, \\dots, v_k$ such that:\r\n- $k \\ge 1$\r\n- there is an edge between nodes $v_i$ and $v_{i+1}$ for each $i$ ($1 \\le i \\le k-1$)\r\n- $v_i \\neq v_j$ for each $i, j$ ($1 \\le i, j \\le k$) such that $i \\neq j$\r\n\r\nYou should find the maximum of values of all simple paths in the given tree.\r\n\r\n### Input\r\n- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\r\n- The first line of each test case contains a single integer $N$.\r\n- The second line contains $N$ space-separated integers $W_1, W_2, \\dots, W_N$.\r\n- Each of the following $N-1$ lines contains two space-separated integers $u$ and $v$ denoting an edge between nodes $u$ and $v$.\r\n\r\n### Output\r\nFor each test case, print a single line containing one integer — the maximum value of a simple path.\r\n\r\n### Constraints\r\n- $2 \\le N \\le 50,000$\r\n- the sum of $N$ over all test cases does not exceed $400,000$\r\n- $1 \\le u, v \\le N$\r\n- $u \\neq v$\r\n- $|W_i| \\le 1,000$ for each valid $i$\r\n- the graph described in the input is a tree\r\n\r\n### Subtasks\r\n**Subtask #1 (30 points):** the tree is a binary tree rooted at node 1\r\n\r\n**Subtask #2 (30 points):**\r\n- the length (number of nodes) of any simple path in the tree is at most $200$\r\n- the sum of $N$ over all test cases does not exceed $100,000$\r\n\r\n**Subtask #3 (40 points):** original constraints"}},{"title":"Sample 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\n"}}]}