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.
|Tags||akashbhalotia, aman_robotics, binary-lifting, dynamic-programming, ico, icop1904, lca, medium|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions