Can anyone please share his/her code of SPOJ problem COT2 - Count on a tree II.
Problem link- http://www.spoj.com/problems/COT2/
Reference- http://codeforces.com/blog/entry/43230
2 Likes
The blog post has explained the approach very well and the author has provided his code at the end of the post. You may have missed it.
1 Like
Well thanks, but I didn’t get that code. I’m trying to figure out from where to start solving problems like COT2.
Here is my code which I wrote sometime back for COT2: link. I’m not sure whether this will help you, because I followed this blog post too and the code is very similar to the author’s, but see for yourself.
For this approach you need to be familiar with DFS (depth first search), fast lookup of LCA (lowest common ancestor) and Mo’s algorithm. Articles on DFS are available in plenty online, for LCA queries the author has used a [sparse table](https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Another%20easy%20solution%20in%20O(N%20logN,%20O(logN)) (but you can use something else too) and for Mo’s algorithm the author has provided the link to a nice tutorial. When you have these under your belt you’ll be prepared to tackle COT2, in my opinion. Good luck 
3 Likes
@meooow, can you answer my query too? (its in “CHEF AND YODA EDITORIAL” thread’s answer of yours. If you have time, I would appreciate that! )
Sure, sorry I hadn’t noticed.
1 Like