You are not logged in. Please login at www.codechef.com to post your questions!

×

COT2 - Count on a tree II - help needed

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

asked 18 Mar '17, 14:22

only4's gravatar image

4★only4
1.5k212
accept rate: 17%

1

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.

(18 Mar '17, 14:53) meooow ♦6★

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

(18 Mar '17, 17:42) only44★

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 (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 :)

link

answered 18 Mar '17, 18:11

meooow's gravatar image

6★meooow ♦
7.3k720
accept rate: 48%

1

Thanks @meooow

(18 Mar '17, 20:16) only44★

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

(18 Mar '17, 20:23) vijju123 ♦♦5★
1

Sure, sorry I hadn't noticed.

(20 Mar '17, 22:14) meooow ♦6★

Now I'm able to understand your code @meooow

(30 Apr '17, 08:40) only44★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,138
×711
×116

question asked: 18 Mar '17, 14:22

question was seen: 1,037 times

last updated: 30 Apr '17, 08:40