# 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

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

QTREE2.cpp

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.

QTREE3.cpp

## Solution $\gamma$

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

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.

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.

QTREE5.cpp