PROBLEM LINK:
Author: Sahil Garg
Tester: Vaibhav Gosain
Editorialist: Sahil Garg
DIFFICULTY:
MEDIUM
PREREQUISITES:
DP
PROBLEM:
Given a tree with n nodes, find the length of longest path such that [1st, (k+1)th, (2*k+1)th,…] node in the path have non-decreasing value.
QUICK EXPLANATION:
This problem can be solved using dp on trees. Say we root the tree at any arbitrary node. Now, for each node u in the tree, if we find the longest path, which satisfies the required property, and :
(a) starts at a node in subtree of u, and ends at u.
(b) starts at u, and ends at a node in subtree of u
(c) starts at a node in subtree of u, passes thorugh u, and ends at a node in subtree of u.
and take maximum of lengths of paths in all three cases for all nodes u in the tree, we will get the required answer.
EXPLANATION:
Let every kth node in a path in the tree be called a ‘special’ node.
DP states are defined as follows:
dp1[u][i][a]: denotes longest path which starts in subtree of node u and ends at u, the last special node is at a distance of i from node u, and the value of last special node is a.
dp2[u][i][a]: denotes longest path which starts at u and ends in subtree of node u, the first special node is at a distance of i from node u, and the value of first special node is a.
The answer for cases (a) and (b) above can be easily found for each node u if we have found the dp values.
Calculating the dp:
If we know the dp values for each child of u,
dp1[u][i][a] = maximum{1+dp1[v][i-1][b] : where v is a child of u, and b<=a}
dp2[u][i][a] = maximum{1+dp2[v][i-1][b] : where v is a child of u, and b>=a}
For case (c) we break the path into 2 parts, iterate over all values of i and a, and for each part coming from subtree of u, we need to find matching longest path going into subtree of u. ‘Matching’ here means that if the incoming path has second parameter as i, the outgoing path will have corresponding parameter as k-1-i.
SAMPLE SOLUTIONS:
Tester’s solution can be found here.