# PROBLEM LINK:

Practice

Contest

**Setter:** Aman Kumar Singh

**Tester:** Aman Kumar Singh, Taranpreet Singh

**Editorialist:** Akash Bhalotia

# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

Dynamic Programming, Lowest Common Ancestor

# PROBLEM:

Given a weighted, rooted Tree with *N* vertices, root is at 1, answer *Q* queries of type *u*, *v*, *x*. Here, *u* and *v* are vertices whose subtrees are disjoint. Find the **maximum weighted path** between *u* and *v*, given that you are allowed to add atmost 1 edge of weight *x* (x is positive) between any vertex of subtree of *u* and any vertex of subtree of *v*.

# USEFUL CONSTRAINTS:

- $1 \leq T \leq 5$
- $1 \leq N,Q \leq 2*10^5$

# QUICK EXPLANATION:

We will compare the weights of exactly two paths. 1) From *u* to *LCA* of (u,v) and from this *LCA* to *v*. 2) From any node in the maximum weight subtree of *u*, connect an edge of weight *x* to any node in the maximum weight subtree of *v*. The maximum of these two is the answer.

# EXPLANATION:

First let's consider the case when we don't add any extra edge. From any node in a tree, there is a unique path to any other node. This path passes through the Lowest Common Ancestor of the two nodes. You can study about LCA from here, or if you like video tutorials, here. These tutorials explain a technique called **Binary Lifting** to find the LCA of two nodes in *O($logN$)* per query. Another technique to find the LCA using **dynamic programming** has been explained here.

We can *precompute* the weighted distance from the root to every other node:

**dist[i] = dist[itsParent]+weightOfThisEdge**.

Once we find the LCA of *u* and *v*, we can find the total weight of the path from *u* to *v*, passing through the LCA using this distance in constant time:

View Content

Hide Content

**lcaPathWeight = (dist[u] - dist[lca]) + (dist[v] - dist[lca])**

Now let us consider the case when we add an edge to connect the subtrees of *u* and *v*. On connecting any vertex of subtree of *u* to that of *v*, we get another path from *u* to *v*. Remember, we need to maximise the weight of the path. This can only be achieved if we connect the maximum weight subtree of *u* to the maximum weight subtree of *v*.

We can compute the maximum weight subtree of every node using **dynamic programming** and DFS. For every node, we compute the maximum weight subtree for each of its children. The maximum of all these is the one with which we shall form our path. We can also decide to not take any children in its path if all their maximum subtree sums are negative as we can have a path from this node to itself, of weight 0. Formally:

**DP[i] = 0.**

DP[i]= max(DP[i], DP[acrossAllChildrenOfi] +weightOfThisEdge)

Thus, for a pair of vertices *u* and *v*, then maximum weighted path through an edge of weight *x* to connect their subtrees :

View Content

Hide Content

**SubtreePathWeight = DP[u] + DP[v] + x**

The maximum of lcaPathWeight and SubtreePathWeight shall give us our answer.

**Note:-**

This problem has tight constraints. It is advisable to avoid recursive steps wherever possible and to also use Fast IO to avoid *TLE* in some languages.

# COMPLEXITY:

DP takes *O(N)*. Binary Lifting takes *O(NlogN)* for precomputation and *O(logN)* per query. Thus

**Time Complexity: ***O(NlogN) + O(QlogN)* per test case
**Space Complexity: ***O(NlogN)* per test case, for Binary Lifting table.

# AC SOLUTIONS:

# SIMILAR PROBLEMS:

Feel free to share your approach if it differs. If you have any doubts, or if you feel stuck at any point, you can ask them below. We would love to hear your suggestions :)

Thanks to @taran_1407 and @vijju123 for their constant guidance and support.