TREEDGE - EDITORIAL

akashbhalotia · January 29, 2019, 6:43pm

PROBLEM LINK:

Practice
Contest

Setter: Aman Kumar Singh
Tester: Aman Kumar Singh, Taranpreet Singh
Editorialist: Akash Bhalotia

DIFFICULTY:

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 the bottom-most node in the maximum weight subtree of u, connect an edge of weight x to the bottom-most 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:

Click to view

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 :

Click to view

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.