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
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”
Special Case: Counting only paths which starts from a particular vertex
This 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:
dfs(int v,int count){
ans = ans + count
for each child u of v{
if(A[parent[v]] < A[v] && A[v] > A[u]){
dfs(u,count+1)
} else {
dfs(u,count)
}
}
}
General description of full solution
The 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

two subpaths of type A having i and j interesting triples, this will result in a path having i+j+1 interesting triples

two subpaths of type B having i and j interesting triples, this will result in a path having i+j+2 interesting triples

two subpaths of type C having i and j interesting triples, this will result in a path having i+j interesting triples

one subpath of type A and one of type B having i and j interesting triples, this will result in a path having i+j+1 interesting triples

one subpath of type A and one of type C having i and j interesting triples, this will result in a path having i+j interesting triples

one subpath of type B and one of type C having i and j interesting triples, this will result in a path having i+j+1 interesting triples
Choosing the best vertex V
if 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 SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.