Sum on Tree

All submissions for this problem are available.
Read problems statements in Mandarin chinese and Vietnamese as well.
You are given a tree with $N$ nodes (numbered $1$ through $N$) and $N1$ edges. Each node has a value; let's denote the value of node $x$ by $W_x$. Next, let's define the value of a simple path $v_1, v_2, \dots, v_k$ as $\sum_{i=1}^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:  $k \ge 1$  there is an edge between nodes $v_i$ and $v_{i+1}$ for each $i$ ($1 \le i \le k1$)  $v_i \neq v_j$ for each $i, j$ ($1 \le i, j \le k$) such that $i \neq j$ You should find the maximum of values of all simple paths in the given tree. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The second line contains $N$ spaceseparated integers $W_1, W_2, \dots, W_N$.  Each of the following $N1$ lines contains two spaceseparated integers $u$ and $v$ denoting an edge between nodes $u$ and $v$. ### Output For each test case, print a single line containing one integer — the maximum value of a simple path. ### Constraints  $2 \le N \le 50,000$  the sum of $N$ over all test cases does not exceed $400,000$  $1 \le u, v \le N$  $u \neq v$  $W_i \le 1,000$ for each valid $i$  the graph described in the input is a tree ### Subtasks **Subtask #1 (30 points):** the tree is a binary tree rooted at node 1 **Subtask #2 (30 points):**  the length (number of nodes) of any simple path in the tree is at most $200$  the sum of $N$ over all test cases does not exceed $100,000$ **Subtask #3 (40 points):** original constraints ### Example Input ``` 3 5 1 2 3 4 5 1 2 2 3 3 4 3 5 2 1 1 1 2 3 1 1000 30 1 3 2 3 ``` ### Example Output ``` 34 1 2941 ```Author:  ratingoverflow 
Editorial  https://discuss.codechef.com/problems/TSUM2 
Tags  centroiddecomp, convexhull, geometry, hard, lines, ltime60, ratingoverflow 
Date Added:  12052018 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 