这题是可以点分治或LCT作的。。但这里讲边分治的做法。。
和点分治类似，边分治利用一条树上路径要吗经过一条边，要么不经过。而不经过的路径必然会在一次分治中变为经过的。
我们找到一条中心边，边左边和边右边分别建一个大根堆。左边的堆中存储边的左子树中白点的深度，右边的堆储存右边的。
当发生颜色反转时，若为黑点转白点，则去掉标记，并将点压入相应的堆中。若为白点转为黑点，则将其打上标记。
统计时，先不断弹左右堆顶，直到堆顶没有标记或堆空。然后用左堆顶值、右堆顶值和(左堆顶值+右堆顶值+中心边长度)三者的最大值更新答案。
为方便边分治，我们使每个点的度数不大于(3)，即转为一棵二叉树。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5, MAXE = 4e6 + 5;
struct {
int v, w, nxt, pre;
} edge[MAXE], _edge[MAXE];
int head[MAXN], _head[MAXN], tot, _tot, tail[MAXN], mark[MAXN], size[MAXN], n, _n, cnt, rt, midedge, maxv;
inline void _add(int u, int v, int w) {_edge[_tot].v = v,_edge[_tot].w = w,_edge[_tot].nxt = _head[u],_head[u] = _tot++;}
inline void add(int u, int v, int w) {edge[tot].v = v,edge[tot].w = w,edge[tot].nxt = head[u],head[u] = tot++;}
inline void del(int u, int i) {
if (head[u] == i) head[u] = edge[i].nxt;
else edge[edge[i].pre].nxt = edge[i].nxt;
if (tail[u] == i) tail[u] = edge[i].pre;
else edge[edge[i].nxt].pre = edge[i].pre;
}
inline void build(int u, int fa) {
int father = 0;
for (int i = _head[u]; ~i; i = _edge[i].nxt) {
int v = _edge[i].v, w = _edge[i].w;
if (v == fa) continue;
if (father == 0)
add(u, v, w),add(v, u, w),
father = u,
build(v, u);
else
mark[++n] = 0,
add(n, father, 0),add(father, n, 0),
father = n,
add(v, father, w),add(father, v, w),
build(v, u);
}
}
inline void get_pre() {
memset(tail, -1, sizeof(tail));
for (int i = 1; i <= n; i++)
for (int j = head[i]; ~j; j = edge[j].nxt) edge[j].pre = tail[i],tail[i] = j;
}
struct point {
int u, dis;
point() {}
point(int _u, int _dis) {u = _u; dis = _dis;}
bool operator <(const point& _A)const {return dis < _A.dis;}
};
struct tree {
int rt, midlen, ans, ls, rs;
priority_queue<point>q;
} t[2*MAXN];
inline void dfs_size(int u, int fa, int dir) {
_add(u, rt, dir);
if (mark[u]) t[rt].q.push(point(u, dir));
size[u] = 1;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v, w = edge[i].w;
if (v == fa) continue;
dfs_size(v, u, dir + w),
size[u] += size[v];
}
}
inline void dfs_midedge(int u, int fa) {
if (max(size[u], size[t[rt].rt] - size[u]) < maxv) maxv = max(size[u], size[t[rt].rt] - size[u]),midedge = fa;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (i != (fa ^ 1)) dfs_midedge(v, i);
}
}
inline void pushup(int rt) {
t[rt].ans = -1;
for (;!t[rt].q.empty() && mark[t[rt].q.top().u] == 0;) t[rt].q.pop();
int ls = t[rt].ls, rs = t[rt].rs;
if (ls == 0 && rs == 0) {
if (mark[t[rt].rt])t[rt].ans = 0;
} else {
if (t[ls].ans > t[rt].ans) t[rt].ans = t[ls].ans;
if (t[rs].ans > t[rt].ans) t[rt].ans = t[rs].ans;
if (!t[ls].q.empty() && !t[rs].q.empty()) t[rt].ans = max(t[rt].ans, t[ls].q.top().dis + t[rs].q.top().dis + t[rt].midlen);
}
}
inline void dfs(int id, int u) {
rt = id,maxv = n,midedge = -1,t[id].rt = u;
dfs_size(u, 0, 0),dfs_midedge(u, -1);
if (~midedge) {
int p1 = edge[midedge].v, p2 = edge[midedge ^ 1].v;
t[id].midlen = edge[midedge].w,t[id].ls = ++cnt,t[id].rs = ++cnt,
del(p1, midedge ^ 1),del(p2, midedge),dfs(t[id].ls, p1),dfs(t[id].rs, p2);
}
pushup(id);
}
inline void update(int u) {
mark[u] ^= 1;
for (int i = _head[u]; ~i; i = _edge[i].nxt) {
int v = _edge[i].v, w = _edge[i].w;
if (mark[u] == 1) t[v].q.push(point(u, w));
pushup(v);
}
}
int main() {
memset(_head, -1, sizeof(_head)),
scanf("%d", &_n);
for (int i = 1, u, v, w; i < _n; i++)
scanf("%d%d%d", &u, &v, &w),
_add(u, v, w),_add(v, u, w);
memset(head, -1, sizeof(head)),
n = _n;
for (int i = 1; i <= n; i++) mark[i] = 1;
build(1, 0),get_pre(),
memset(_head, -1, sizeof(_head)),
_tot=0,
dfs(cnt = 1, 1);
char op[2]; int m, x;
scanf("%d", &m);
for(;m;--m) {
scanf("%s", op);
if (op[0] == 'A')
if (t[1].ans == -1) printf("They have disappeared.
");
else printf("%d
", t[1].ans);
else
scanf("%d", &x),
update(x);
}
return 0;
}