QTREE

Problem

CHANGE i ti : change the cost of the i-th edge to ti
or
QUERY a b : ask for the maximum edge cost on the path from node a to node b

Solution

树链剖分$O(nlg^2 n)$

Code

QTREE.cpp

QTREE2

DIST a b : ask for the distance between node a and node b
or
KTH a b k : ask for the k-th node on the path from node a to node b

Solution $\alpha$

倍增

Code

QTREE2.cpp

Solution $\beta$

LCT

QTREE3

Problem

0 i : change the color of the i-th node (from white to black, or from black to white);
or
1 v : ask for the id of the first black node on the path from node 1 to node v. if it doesn’t exist, you may return -1 as its result.

Solution $\alpha$

考虑维护每个点到根节点链上的黑点个数，使用DFS序+树状数组

然后对于每个询问树上二分即可

时间复杂度$O(nlg^2 n)$

Code

QTREE3.cpp

Solution $\beta$

树链剖分，线段树上每个线段维护最左边的黑点

时间复杂度$O(nlg^2 n)$

Solution $\gamma$

LCT，询问即在到根的链的Splay上查询第一个黑点

时间复杂度$O(nlgn)$

Code

QTREE3-LCT.cpp

QTREE4

Problem

C a : change the color of node a.(from black to white or from white to black)
A : ask for the maximum dist(a, b), both of node a and node b must be white(a can be equal to b). Obviously, as long as there is a white node, the result will alway be non negative.

Solution

动态点分治

设分治到一个连通块时的根为root

对它的每一棵子树用堆维护最大的白点到root的距离，用其中的最大值更新下面这个堆：

对每一个root用堆维护最大的白点到root的距离，并用堆中最大的两个值的和更新下面这个堆：

每个root的最优解用堆维护

以上所有堆都为可删堆

Code

QTREE4.cpp

QTREE5

Problem

0 i : change the color of i-th node(from black to white, or from white to black).
1 v : ask for the minimum dist(u, v), node u must be white(u can be equal to v). Obviously, as long as node v is white, the result will always be 0.

Solution

类似于QTREE4的Solution，似乎是简化版

Code

QTREE5.cpp