I am confused with the query part,
how it is computing the answer for only those nodes which are in the path and neglecting other nodes in the path either left or right child
1 Like
First thing first. Learn about eulerian path on tree. If we use that trick, we can access only the nodes of a particular subtree we desire.
In other words, we convert the tree into an array, then you segment tree on the array.
We don’t need lazy prop here right?
Use tries.
No it should work without lazy prop.
I only know how to do it with lazy prop. Is there any other way ?
I tried both techniques,
-
Point Update and Range Query
link :- CodeChef: Practical coding for everyone -
Range Update and Point Query
link :- CodeChef: Practical coding for everyone
https://www.codechef.com/viewsolution/29242886
Can anyone please debug this ? Code is very clean 
I checked with a lot of test cases but couldnt find anything wrong.But it is giving wrong answer .
Fails on this-
4 2
1 2
1 3
2 4
1 2 3 4
2 1 3
1 1
Basically any update on node 1 is useless because we only have to add when we land on a node and that never happens for node 1 , so you can just skip the updates
Hello Karan , I had seen your youtube channel. The video you made on the topic " DP " is awesome. It cleared my concept /approach to solve Dp problems easily. Thanks for sharing your knowledge 
. If possible please make more such videos on other topics too. Thanks a lot again.
1 Like
Can you explain what you did after inserting all the strings inside the trie. How does it help?
You check if a string is made up of other strings aldready present in the trie by going over every characters of the string. Since in the problem the length of the string was of the range 10K hence using the DP/DFS approach using substring method would result in TLE as finding substring was essentially becoming a O(N) operation which can be avoided by using a trie to check for substring. If you need help with implementation, I will be uploading the editorial soon!
2 Likes