某岛

… : "…アッカリ～ン . .. . " .. .

August 2, 2012

【套题】QTREE 系列

Brief description:

… QTREE 系列一共 5 题，都是与树有关的数据结构题：
… QTREE 是最经典的树链剖分模型，有极多的派生，必须仔细研究并熟练掌握所有方法。。。
QTREE2 的解法要利用到倍增祖先数组，这也是一个比较常见的策略，可以用来解决诸如次小生成树之类的问题。。
QTREE3~5 涉及黑白树问题，既树中每个点分成黑色和白色，
QTREE3 询问距离根结点最近的黑色结点，QTREE4 询问全局最远的两个白色结点，QTREE5 询问距离某结点最近的白色结点。。
（其中 QTREE4 是整个系列中最困难的一题，建议先调试好没有边权的 Hide 。。
（另外 QTREE3 有正版和盗版之分。。为整理方便。。。正版的 QTREE3 也就是 PT07J 将放在 Play With Tree 系列的报告里。。。