COT2 - Count on a tree II - help needed

general
, ,
1

Can anyone please share his/her code of SPOJ problem COT2 - Count on a tree II.

Problem link- SPOJ.com - Problem COT2

Reference- Mo's Algorithm on Trees [Tutorial] - Codeforces

2 Likes
2

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](Topcoder) (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 :slight_smile:

3 Likes
3

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
4

Well thanks, but I didn’t get that code. I’m trying to figure out from where to start solving problems like COT2.

5

Thanks @meooow

1 Like
6

@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! :slight_smile: )

7

Sure, sorry I hadn’t noticed.

1 Like
8

Now I’m able to understand your code @meooow