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

×

SPOJ QTREE4

Could someone help me understand and solve SPOJ QTREE4.

I've solved QTREE1-3 using HLD and Segment trees but the same approach doesn't seem to work in this one. Since, we need to find the longest shortest distance between any two white nodes in a tree usual segment tree methods aren't working for me.

Can centroid decomposition be used in this question? If yes could someone please explain me how. I couldn't find any good resources for the same apart from this link- http://codeforces.com/blog/entry/10533

asked 26 Jun '14, 22:48

nitinj's gravatar image

5★nitinj
2.2k112027
accept rate: 5%


This link: https://www.quora.com/What-is-the-approach-to-solve-the-SPOJ-problem-QTREE4 describes a nice solution using Centroid Decomposition, although more tough to implement than SPOJ QTREE 1-3.

link

answered 05 Mar '18, 22:25

sinbycos's gravatar image

3★sinbycos
332
accept rate: 0%

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
×116
×109
×42
×1

question asked: 26 Jun '14, 22:48

question was seen: 3,021 times

last updated: 05 Mar '18, 22:25