【套题】QTREE 系列

Brief description:

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

ゆっくり読んでください …