maybe the equation above need some fix.
For those who need a tutorial on binary lifting. I learnt it pretty much from here: Episode 17 - Binary Lifting - YouTube
Solution for this problem with binary lifting is great and the overall runtime is O(nlogn) since you find the vertex y of any vertex x in O(logn). I have a similar solution but I can reduce the runtime down to O(n). You can see the implementation here: c++.
Here is a short explaination. This problem reminds me about the easier version of this problem that when the tree is a segment, the vertex y of any vertex x can be found using stack. My solution using a persistent-like stack. When you DFS to a child, you save the stack of the parent, and when you go back to the parent, just do rollback and continue DFS to another child. In my implementation, the operation push, pop, save and rollback run in O(1). Each vertex you have to push it in the stack 1 time and the number of time you pop a vertex x equals to the direct child of the x. Since sum of direct child of all vertex equals to the number of the edges, that is, n - 1, hence overall complexity is O(n + n - 1) = O(n).
4 Likes
In the above equation i think,
it should be DP(x)=DP(Parent[y])+(cnt[x]−cnt[Parent[y])∗A[x].
2 Likes
I too think the same hacker_sk
In the above code,
val[x][0] = min(A[x], A[Parent[x]])
for ( i = 1 to 19 ) {
if ( up[x][i] != -1 ) {
val[x][i] = min(val[x][i - 1], val[val[x][i - 1]][i - 1])
}
}
I think it should be,
val[x][0] = min(A[x], A[Parent[x]])
for ( i = 1 to 19 ) {
if ( up[x][i] != -1 ) {
val[x][i] = min(val[x][i - 1], val[up[x][i - 1]][i - 1])
}
}
1 Like
Kindly someone please help me in finding the test case for which my code fails. All that i have tested passed but it is getting WA on submission. Link to my solution is CodeChef: Practical coding for everyone
implementation of editorial in C++ given below:
https://www.codechef.com/viewsolution/13905914
1 Like
@darkkcyan This is indeed a good approach. But the worst case time complexity of this solution is O(n^2). Look at this test case:
15
1 2 3 4 5 6 7 8 8 8 8 8 8 8
93 94 95 96 97 98 99 100 1 2 3 4 5 6 7.
The while loop inside the dfs function runs n/2 times for all n>=9 i.e for n/2 times.
Hence the time complexity is O(n+(n/2)*(n/2))=O(n^2). Correct me if I am wrong. Cheers ! 
as mentioned in the editorial:
Now, for calculating the answer for node x, we need to find the greatest ancestor y of x in path from 11 to Parent[x]Parent[x], where all the nodes in path from x to y have their values greater than or equal to the given value of the node x.
Is there a constraint that nodes in path from x to y NEED to have their values(which are given during input) greater than or equal to the given value of the node x?
why doesn’t the setters code work??
weak test cases , even brute-force is passing the problem with a runtime of 0.06 which is having time limit of 2.0 sec !
my solution: posttree soln
i tried this but getting WA in the last test case of second subtask…
if possible please help me with my code…
can anyone please explain a little bit how counts array is built?
i have implemented without this with the help of binary search ! but want to know this !
https://www.codechef.com/viewsolution/17201285
My solution using simple DP and dfs. I basically created two arrays, one storing all forward node information and the other one storing all backward node info.
Yes. Even I was thinking on the similar lines during contest, but wasn’t able to design a proper solution. Nice Solution
1 Like
Kindly someone please help.I am unable to find a bug in my approach.Link to my solution is already posted.If someone can find the test case for which my code fails it would be of great help for finding the failure point in the code.
Thanks, corrected.
Thanks, corrected.