Zero the Path

All submissions for this problem are available.
You are given a tree with $N$ nodes with a number written on each node. A pathsum for any two nodes is defined as the sum of the values written at all nodes in the simple path between the two nodes. In particular if both the chosen nodes are same then pathsum is the value at the node itself. Find the maximum possible pathsum between any two nodes in the given tree if you can perform the following operation at most once before calculating the pathsum: * Choose a simple path between any two nodes and make the value written on all the nodes on that path equal to $0$. ###Input:  First line will contain $T$, number of test cases.  First line of each test case will contain $N$, number of nodes in the tree.  Next line contains $N$ spaceseparated integers  $A_1, A_2, ..., A_N$, denoting the value written on each node.  Next $N1$ lines will contain two integers each  $u$ and $v$ denoting an undirected edge between $u$ and $v$. ###Output: For each test case, output in a new line the maximum possible pathsum. ###Constraints  $1 \leq T \leq 5$  $1 \leq N \leq 10^5$  $10^9 \leq A_{i} \leq 10^9$ ###Sample Input 2 4 2 1 5 2 1 2 2 3 1 4 4 1 2 3 4 1 2 2 3 1 4 ###Sample Output 7 10 ###EXPLANATION For testcase 1, the tree given in the input is shown below: ![Image 1](https://codechef_shared.s3.amazonaws.com/download/HYC/External_contest_i... =500x300) The maximum path sum possible for now is $5$. But if we choose the path between nodes $1$ and $2$ and make the values of the nodes as $0$, the tree now becomes: ![Image 1](https://codechef_shared.s3.amazonaws.com/download/HYC/External_contest_i... =500x300) The maximum possible path sum now is $7$ (Between nodes $3$ and $4$)Author:  aayush1998 
Tags  aayush1998 
Date Added:  21082019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions