PROBLEM LINK:DIFFICULTY:MediumHard PREREQUISITES:divide and conquer, trees, DFS PROBLEM:Given a tree of N vertices and two integers L and R, ith vertex of the tree has value a_{i}, you are required to count the number of simple paths v_{1}, v_{2}, ..., v_{K} such that the number of indices j with 1 < j < K with a_{vj1} < a_{vj} and a_{vj} > a_{vj+1} is at least L and at most R. SHORT EXPLANATION:let's call a triple of 3 consecutive vertices in a path such that a_{vj1} < a_{vj} and a_{vj} > a_{vj+1} by "interesting triple" We will use divide and conquer on tree to solve this problem, first we find the centroid node of the tree then try to count the required paths which passes through the centroid node then we delete it and solve the same problem problem on every subtree created after deleting. to count number of paths required which passes through the centroid, first we do DFS from the centroid to count the paths which start at the centroid itself, then we need to consider the case when the centroid is in the middle of the path, in other words that path consists of two subpaths plus vertex V, so we maintain 3 arrays A, B, C, A_{i} means the number of paths which have i interesting triples and start at neighbor of V and that neighbor have value less than V B_{i} means the number of paths which have i interesting triples and start at neighbor of V and that neighbor have value bigger than V but second vertex at this path is less than that neighbor C_{i} means the number of paths which have i interesting triples and start at neighbor of V and that neighbor have value bigger than V but second vertex at this path is not less than that neighbor then we count the number of pairs of those paths which will make a path passing through vertex V and having between L and R triples EXPLANATIONlet's call a triple of 3 consecutive vertices in a path such that a_{vj1} < a_{vj} and a_{vj} > a_{vj+1} by "interesting triple" Special Case: Counting only paths which starts from a particular vertexThis special case will help us to solve the problem in O(N^2) and thus get partial score, and also it's a part of the approach of the full solution. To count the paths which starts at a given vertex V, we root the tree at the vertex V then do a recursive dfs and hold some parameter how many interesting triples found so far, here's pseudo code for it:
General description of full solutionThe full solution to this problem is called divide and conquer on tree, if we pick some vertex V from the tree then all paths will either pass from V or will be completely contained in one of the subtrees which will be formed if we delete vertex V so the idea would be to select some node v then count all interesting paths which passes through it then delete that vertex and solve the problem recursively for each subtree remained after deleting V, selecting best vertex V is critical in order to make the complexity of our solution faster than O(N^2) paths which pass through vertex V have two cases, first vertex V is the first node on that path then we can count them just like what is described in previous paragraph, second for paths in which vertex V is in the middle of it then we notice that the path will start at one subtree then reach v then go again to another subtree, in other words those paths consist of two subpaths plus vertex V, so the idea is count those subpaths then we count how many pairs of subpaths can be paired in such a way the number of interesting triples is between L and R, we have 3 types of subpaths so we obtain 3 arrays: A_{i} means the number of paths which have i interesting triples and start at neighbor of V and that neighbor have value less than V B_{i} means the number of paths which have i interesting triples and start at neighbor of V and that neighbor have value bigger than V but second vertex at this path is less than that neighbor C_{i} means the number of paths which have i interesting triples and start at neighbor of V and that neighbor have value bigger than V but second vertex at this path is not less than that neighbor they can be obtained by DFS similar to one above, now we should look at possible pairing of the subpaths
Choosing the best vertex Vif we choose the vertex V in such a way that every remaining subtree after deleting vertex V will have size at most half size of the current tree then our recursion will have at most O(log N) layers each, layer will take O(N) time so in total complexity would be O(N log N) but how to find such a vertex? it can be proved that such a vertex always exists for any tree the description of the algorithm to find it can itself work as a proof and this vertex is call centriod vertex Let's start at an arbitrary vertex V, and make it the root of the tree then we compute the size of every subtree in that tree, now let's check is there a child of vertex V having in its subtree more than half of vertices of subtree of V? if no then we are done because vertex V is the centriod vertex if no then there would be at most one such child, so we visit that child and repeat until we find the centroid SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 13 Nov '16, 03:18

Why 20 testcases with N=50000? Using fewer testcases with a higher number of N would definitely have discriminated asymptotically subotimal solutions far better. I used a different approach (the editorialists's approach is far better so no need to discuss it) submitting a preliminary version with $O(n^2)$ worstcase behaviour and it easily passed. answered 16 Nov '16, 19:06

You can see my submission following the same centroid decomposition method described in the editorial: https://www.codechef.com/viewsolution/12097460 And if you want to read more about centroid composition and where you can apply it, you can check my editorial to one of the problems from October Lunchtime here: https://discuss.codechef.com/questions/86796/countieseditorial answered 17 Nov '16, 02:48

I have a similar solution but it is O(N * log N * log N). Extra log N is for BIT. looks like tester's solution is also the same. In the editorial it's claimed as O(N * log N), how is that? Thanks :) answered 20 Nov '16, 20:44

Given Setter's solution is O(n^2) and it is giving TLE. Can you please check that again. answered 29 Nov '16, 17:50

My approach is quite different from the editorial, but its giving wrong answer and I am clueless where it is wrong. Code : answered 18 Nov '16, 19:24

I uset BIT for solving this ;) https://www.codechef.com/viewsolution/16007035 answered 29 Oct '17, 21:12
