QTREE系列题目，是SPOJ上的一系列数据结构题，共有6题，名称依次是QTREE1~5，其中QTREE3有盗版和正版之分……题目会给定一棵树，要求你回答树上的各种询问。
下面是QTREE1~5我的AC记录
解题报告：
QTREE
原题地址 http://www.spoj.pl/problems/QTREE/
给定一棵n个结点的树，树的边上有权。你被要求支持：
1.修改一条边上的权值。
2.查询两个结点x和y之间的最短路径中经过的最大的边的权值。
其中n<=10^4.
很明显的这题是树的轻重边路径划分（树链剖分）的练手题。
QTREE2
原题地址http://www.spoj.pl/problems/QTREE2/
给定一棵n个结点的树，树的边上有权。你被要求支持：
1.查询两个结点x和y之间的最短路径长度。
2.查询从x到y的最短路径的第K条边的长度。
其中n<=10^4.
因为没有修改操作，这题其实和树链剖分一点关系没有。设p[i,j]表示结点i的第2^j个祖先的编号。这显然可以通过一个O(nlgn)的预处理求出。然后求最近公共祖先（lca）就是O(lgn)每次了。设dist[i]表示从结点1到结点i的距离。然后显然对于操作1，答案为dist[x]+dist[y]-dist[lca[x,y]]*2；而对于操作2，答案可以通过利用p数组通过倍增在O(lgn)内求出。于是问题得到了解决。
盗版QTREE3
原题地址 http://www.spoj.pl/problems/QTREE3/
给定一棵n个结点的树，树的每个结点有黑白两色，初始时所有的结点都是白的。你被要求支持：
1.对一个结点执行反色操作（白变黑，黑变白）
2.查询从1号结点到i号结点的路径上的第一个黑色结点编号。
其中n<=10^5. 查询数目不超过10^5.
这显然用树链剖分可以解决，其实甚至比QTREE都要简单，因为没有了轻边，只剩下了重链要维护。这可以用线段树或树状数组或堆方便的解决。
前几天听说了这题一种很强悍的树状数组维护dfs序列的解法。每当一个结点被染色时，就把该子树对应的区间所有数加一。这样在查询时可以通过倍增祖先和一些技巧解决。时间复杂度依然是O(nlgn+Qlg^2n).（这个解法是广陵lonely散神犇提出的，在此膜拜一下。表示我没有写这个解法……但觉得应该没有太大的问题）
正版QTREE3
原题地址https://www.spoj.pl/problems/PT07J/
囧……因为我太傻×，到现在才知道原来QTREE3是这一题……
给定一棵有根树，树根为1，树的点上有权，要求支持查询以某个点为根的子树中第K大的权值。
因为没有修改操作，这题就是很裸的划分树维护DFS序列……注意常数优化即可。
QTREE4
原题地址 http://www.spoj.pl/problems/QTREE4/
给定一棵n个结点的树，树的边上有权，每个结点有黑白两色，初始时所有的结点都是白的。你被要求支持：
1.对一个结点执行反色操作（白变黑，黑变白）
2.查询树中距离最远的两个白点的距离。
其中n<=10^5，查询数目不超过10^5.
这题可以用树链剖分解决。主的分治思想是对于一条重链，最远距离有可能经过或不经过这条重链。不经过的情况可以分治处理。对于经过的情况，可以用线段树+堆维护。具体可以参见漆子超的论文。这题是个好题目。不仅锻炼代码能力，而且可以对树链剖分的本质有更深的理解。
QTREE5
原题地址 http://www.spoj.pl/problems/QTREE5/
给定一棵n个结点的树，边权均为1。每个结点有黑白两色，初始时所有结点都是黑的。你被要求支持：
1.对一个结点执行反色操作（白变黑，黑变白）
2.查询距离某个特定结点i最远的白点的距离。
其中n<=10^5，查询数目不超过10^5.
这题显然像QTREE4一样链分治也是可以的。但其实边分治对这题也是适用的，而且编程复杂度更小。考虑当把一棵树通过中心边分治成两棵子树时，距离某个点i（假设这个点在其中一颗子树中）最远的白点距离可能是：1.在另一棵子树中，显然最远距离是dist[i到这棵子树的根]+1+另一棵子树的根到其子树内某个白点的最远距离。2.在自身所在的子树中，这可以继续分治处理。
于是，我们的任务就变成了维护各个分治子树中的白点距离根的距离，要求支持插入、删除、取最大值。这显然用堆可以完成，但考虑到边权均为1，也就是最大可能的距离不会很大，所以用树状数组是更好的选择。
当修改时，对包含该点的每个子树处理。时间复杂度O(lg^2n)。当查询时，类似的，对包含该点的每个子树查询，取最大值即可，时间复杂度依然为O(lg^2n)。
加点（通过添加无用点把每个点度数降到3以内）是必须的……然后要注意常数优化……表示我开始时偷懒没加点，结果被极端数据搞掉了……然后加了点，常数却写大了还是tle……最后搞了若干常数优化终于ac。然后发现光荣的垫底了……看来边分治虽然好写，但时间复杂度容易退化，常数也很大。唉，一等价钱一等货啊。