【套題】QTREE 系列

Brief description:

… QTREE 系列一共 5 題,都是與樹有關的數據結構題:
… QTREE 是最經典的樹鏈剖分模型,有極多的派生,必須仔細研究並熟練掌握所有方法 。。。
QTREE2 的解法要利用到倍增祖先數組,這也是一個比較常見的策略,可以用來解決諸如次小生成樹之類的問題。。
QTREE3~5 涉及黑白樹問題,既樹中每個點分成黑色和白色,
QTREE3 詢問距離根結點最近的黑色結點,QTREE4 詢問全局最遠的兩個白色結點,QTREE5 詢問距離某結點最近的白色結點。。
(其中 QTREE4 是整個系列中最困難的一題,建議先調試好沒有邊權的 Hide 。。
(另外 QTREE3 有正版和盜版之分。。為整理方便。。。正版的 QTREE3 也就是 PT07J 將放在 Play With Tree 系列的報告里。。。

Analysis:

Level 1:
QTREE 1

Level 2:
QTREE 2

Level 3:
QTREE 3QTREE 4QTREE 5

External link:

http://www.spoj.pl/problems/QTREE/
http://www.spoj.pl/problems/QTREE2/
http://www.spoj.pl/problems/QTREE3/
http://www.spoj.pl/problems/QTREE4/
http://www.spoj.pl/problems/QTREE5/

http://hi.baidu.com/sillycross/blog/item/b5d482cb51277e710eb34567.html