You are not logged in. Please login at www.codechef.com to post your questions!

×

TREEDGE - EDITORIAL

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

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

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.

This question is marked "community wiki".

asked 29 Jan, 18:43

akashbhalotia's gravatar image

4★akashbhalotia
68112
accept rate: 14%

edited 29 Jan, 21:19

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,169
×1,672
×253
×177
×57
×31
×28

question asked: 29 Jan, 18:43

question was seen: 501 times

last updated: 29 Jan, 21:19