Author: Shivam Garg
DIFFICULTY
MEDIUM HARD
PREREQUISITES
DP on Trees
PROBLEM
Given a tree with N nodes, and with each of the N-1 edges having a value associated with it. M of the edges can be traversed atmost twice , while others atmost once. A path has to be chosen such that it takes the longest time to traverse. Tell this longest time possible.
EXPLANATION
This question requires knowledge of DP on Trees. So, I would advise you to go through this tutorial once.
Consider any arbitrary node to be the root of the tree.
dp(x,m) will store the length of the longest path starting from x under these 3 cases -
-
m = 0 : The path will begin from x, go via its subtree and return back to x itself.
-
m = 1 : The path will begin from x, and ends in a node which is part of subtree of x.
-
m = 2 : The path begins in a node in subtree of x, passes through x, and ends in a node in subtree of x. These two nodes need not be different.
Consider y be a child of x, and the connecting edge between the two be e of length l.
Let’s consider the given 3 cases of all the paths passing through both the nodes x as well as y -
-
Loop (Path starts and ends in x): If e can be traversed twice, start at node x, go through e, traverse dp(y,0), then go through e again and come back to x. The length len_0 of the longest loop passing through node y will be \left\{\begin{matrix} 2l + dp(y,0) && traverseTwice(e)=1 \\ 0 && traverseTwice(e)=0 \end{matrix}\right..
-
1 Broken End in Loop (Path starts in x and ends in subtree of y): Start at node x, go through e, then traverse dp(y,0) or dp(y,1). The length len_1 of the longest 1 Broken End through node y will be l+max(dp(y,0), dp(y,1)).
-
2 Broken End in Loop (Path starts as well as ends in subtree of y): If e can be traversed twice, traverse any of the dp(y,0), dp(y,1) or dp(y,2), and add the path of y \rightarrow x \rightarrow y. The length len_2 of the longest 2 Broken End through node y will be \left\{\begin{matrix} 2l + max(dp(y,0), dp(y,1), dp(y,2)) && traverseTwice(e)=1 \\ 0 && traverseTwice(e)=0 \end{matrix}\right..
For finding out dp(x,0), the path will comprise entirely loops through all the children. Hence, dp(x,0) = \sum len_0(y).
For finding out dp(x,1), the path remains almost same as that in dp(x,0).
However, one of the loops through the children must be replaced with a 1 Broken End. In order to find which child will lead to maximum advantage, compute len_1(y) - len_0(y) for each of the child y of node x.
Let that child for which this value is maximum be y_{max}.
Therefore, dp(x,1) = dp(x,0) - len_0(y_{max}) + len_1(y_{max})
For finding out dp(x,2), the path remains almost same as that in dp(x,0).
However, any of the following 2 cases must follow -
-
One of the loops through the children must be replaced with a 2 Broken End.
In order to find which child will lead to maximum advantage, compute len_2(y) - len_0(y) for each of the child y of node x.
Let that child for which this value is maximum be y_{max1}. -
Two of the loops through the children must be replaced with two 1 Broken End.
In order to find which two distinct children will lead to maximum advantage, compute len_1(y) - len_0(y) for each of the child y of node x.
Let those two children be y_{max2} and y_{max3}.
Hence, dp(x,2) = max\left\{\begin{matrix} dp(x,0) - len_0(y_{max1}) + len_2(y_{max1}) \\ dp(x,0) - len_0(y_{max2}) + len_1(y_{max2}) - len_0(y_{max3}) + len_1(y_{max3}) \end{matrix}\right.
The answer is maximum of max (dp(x,0), dp(x,1), dp(x,2)) for all nodes x in the tree.
The number of operations remain O(N).