某岛

… : "…アッカリ~ン . .. . " .. .
August 2, 2012

【套题】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