# 「Query on a tree」

Query on a tree I 维护一棵树，支持修改边权和路径最大值查询
Query on a tree II 维护一棵树，支持链上求和，链上第 K 个位置查询
Query on a tree III 维护一棵树，支持查询子树中的第 K 小节点
Query on a tree again 维护一棵树，支持查询链上深度最小有效节点
Query on a tree IV 维护一棵树，支持查询树上有效点对间的最大距离

## Query on a tree IV

You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3…,N. Each edge has an integer value assigned to it(note that the value can be negative). Each node has a color, white or black. We define dist(a, b) as the sum of the value of the edges on the path from node a to node b.
All the nodes are white initially.

We will ask you to perfrom some instructions of the following form:

• 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.

### 题意

维护一个边带权，点带色的树，支持修改点的颜色以及查询树上最长距离


### 题解

#### 代码1

• 自己打的垃圾点分治，被卡 $TLE$，暂时无法 $AC$

#### 代码2

• $Sengxian$大佬的链分治，详情见 $qzc$ 论文

#### 代码3

• 不知名的神奇代码，速度 $Vjudge~Rank~1$