Tree and Extra Edge

All submissions for this problem are available.
You have a rooted tree consisting of $n$ vertices. There are some weights on each edge of the tree denoted by $W_i$. The tree root is a vertex with number $1$. In this problem, you need to answer $Q$ queries. Each query is described by three values $u$, $v$, and $x$. It is guaranteed that subtrees of node $u$ and node $v$ are disjoint. You are allowed to add at most one edge of weight $x$ between any node in the subtree of $u$ and any node in the subtree of $v$. Find the $maximum$ weighted path between $u$ and $v$ given that each node can occur only once in a path. A subtree of some vertex is a subgraph containing that vertex and all its descendants. ###Input:  First line will contain $T$, number of testcases. Then the testcases follow.  First line of each testcase will contain $N$ and $Q$, number of nodes and queries respectively.  Next $N$ $−$ $1$ lines contain three integers $u$, $v$ and $W_i$ representing an edge between nodes $u$ and $v$ of weight $W_i$.  The next $Q$ lines contain three integers $u$, $v$ and $x$ as explained in the problem statement. ###Output: For each query, output in a single line the $maximum$ weighted path. ###Constraints:  $1 \leq T \leq 5$  $1 \leq n, q \leq 2 * 10^5$  $1 \leq u , v \leq n$  $1 \leq abs(W_i), x \leq 10^9$ ###Subtasks  20 points : $1 \leq n, q \leq 1000$  80 points : $1 \leq n, q \leq 2 * 10^5$ ###Sample Input: 1 7 3 1 2 1 1 3 2 2 4 3 2 5 4 5 7 5 3 6 6 2 3 1 5 4 2 5 6 0 ###Sample Output: 10 7 5 ###Explanation: ![ ](https://codechef_shared.s3.amazonaws.com/download/HYC/External_contest_i...) Query 1 : Its optimal to add a edge between nodes 4 and 6 making a path 2 > 4 > 6 > 3 with a weight of 3 + 1 + 6 = 10.Author:  aman_robotics 
Editorial  https://discuss.codechef.com/problems/TREEDGE 
Tags  akashbhalotia, aman_robotics, binarylifting, dynamicprogramming, ico, icop1904, lca, medium 
Date Added:  13012019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions