题意：有一棵数，每个节点有颜色，黑色或者白色，树边有边权，现在有2个操作，1修改某个点的颜色， 2询问2个白点的之前的路径权值最大和是多少。
题解：
边分治思路。
1.重构图。 因为边分治在菊花图的情况下情况不理想，所以需要先把图重新构建一下，是每个点的度数不超过3。
2.找在新图里面 一条边使得 断开这条边的情况下，左右2新树使得较大的那个子树是所有情况下的最小值。
3.开2个优先队列去维护左边新树的白点的最大值， 右边新树的所有白点的最大值， 然后 左边白点+右边白点+中间边就是最大值。
4.对于2个新图都执行 2-3的操作。
代码：
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 2e5 + ;
struct Node{
int head[N]; int to[N<<];
int ct[N<<]; int nt[N<<];
int tot;
void init(){
tot = ;
memset(head, -, sizeof(head));
return ;
};
void add(int u, int v, int val){
to[tot] = v; ct[tot] = val;
nt[tot] = head[u]; head[u] = tot++;
return ;
}
}e[];
int n, u, v, w;
void rebuild(int o, int u){
int ff = ;
for(int i = e[].head[u]; ~i; i = e[].nt[i]){
v = e[].to[i], w = e[].ct[i];
if(v == o) continue;
if(!ff){
e[].add(u, v, w);
e[].add(v, u, w);
ff = u;
}
else {
++n;
e[].add(ff, n, );
e[].add(n, ff, );
e[].add(v, n, w);
e[].add(n, v, w);
ff = n;
}
rebuild(u, v);
}
return ;
}
vector<pll> vc[N];
priority_queue<pll> pq[N<<][]; int wedge[N<<];
int white[N], sz[N];
int cut[N<<];
int id, maxnum = ;
void get_edge(int o, int u, int num){
sz[u] = ;
int tmp = ;
for(int i = e[].head[u]; ~i; i = e[].nt[i]){
int v = e[].to[i];
if(v == o || cut[i>>]) continue;
get_edge(u, v, num);
sz[u] += sz[v];
tmp = max(num-sz[v], sz[v]);
if(tmp < maxnum){
id = i;
maxnum = tmp;
}
}
return ;
}
int k = , op;
void dfs(int o, int u, int w){
sz[u] = ;
if(white[u]){
pq[k][op].push(pll(w, u));
if(op == ) vc[u].push_back(pll(-k, w));
else vc[u].push_back(pll(k, w));
}
for(int i = e[].head[u]; ~i; i = e[].nt[i]){
int v = e[].to[i];
if(v == o || cut[i>>]) continue;
dfs(u, v, w+e[].ct[i]);
sz[u] += sz[v];
}
return ;
}
int ans[N], lch[N], rch[N];
void update(int k){
while(!pq[k][].empty() && !white[pq[k][].top().se]) pq[k][].pop();
while(!pq[k][].empty() && !white[pq[k][].top().se]) pq[k][].pop();
if(pq[k][].empty() || pq[k][].empty())
ans[k] = ;
else {
int val1 = pq[k][].top().fi, val2 = pq[k][].top().fi;
int sum = val1 + val2 + wedge[k];
ans[k] = max(sum, );
}
if(lch[k]) ans[k] = max(ans[k], ans[lch[k]]);
if(rch[k]) ans[k] = max(ans[k], ans[rch[k]]);
return ;
}
int solve(int u, int num){
if(num == ) return ;
maxnum = inf;
get_edge(, u, num);
int now = ++k, nid = id;
cut[nid >> ] = ;
wedge[k] = e[].ct[nid];
op = ;
dfs(, e[].to[nid], );
op = ;
dfs(, e[].to[nid^], );
lch[now] = solve(e[].to[nid], sz[e[].to[nid]]);
rch[now] = solve(e[].to[nid^], sz[e[].to[nid^]]);
update(now);
return now;
}
void setWhite(int u){
for(int i = vc[u].size()-; i >= ; --i){
pll tmp = vc[u][i];
int k = tmp.fi, ct = tmp.se;
if(k < ) pq[-k][].push(pll(ct, u));
else pq[k][].push(pll(ct, u));
update(abs(k));
}
return ;
}
void setBlack(int u){
for(int i = vc[u].size()-; i >= ; --i)
update(abs(vc[u][i].fi));
return ;
}
int main(){
scanf("%d", &n);
int white_num = n, q;
char op[];
e[].init(); e[].init();
for(int i = ; i < n; i++){
scanf("%d%d%d", &u, &v, &w);
e[].add(u, v, w);
e[].add(v, u, w);
white[i] = ;
}
white[n] = ;
rebuild(, );
solve(, n);
scanf("%d", &q);
while(q--){
scanf("%s", op);
if(op[] == 'A') {
if(white_num == ) puts("They have disappeared.");
else if(white_num == ) puts("");
else printf("%d\n", ans[]);
}
else {
scanf("%d", &u);
white[u] ^= ;
if(white[u])
setWhite(u), ++white_num;
else
setBlack(u), --white_num;
}
}
return ;
}
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 2e5 + ;
struct Node{
int head[N]; int to[N<<];
int ct[N<<]; int nt[N<<];
int tot;
void init(){
tot = ;
memset(head, -, sizeof(head));
return ;
};
void add(int u, int v, int val){
to[tot] = v; ct[tot] = val;
nt[tot] = head[u]; head[u] = tot++;
return ;
}
}e[];
int n, u, v, w;
void rebuild(int o, int u){
int ff = ;
for(int i = e[].head[u]; ~i; i = e[].nt[i]){
v = e[].to[i], w = e[].ct[i];
if(v == o) continue;
if(!ff){
e[].add(u, v, w);
e[].add(v, u, w);
ff = u;
}
else {
++n;
e[].add(ff, n, );
e[].add(n, ff, );
e[].add(v, n, w);
e[].add(n, v, w);
ff = n;
}
rebuild(u, v);
}
return ;
}
vector<pll> vc[N];
priority_queue<pll> pq[N<<][]; int wedge[N<<];
int white[N], sz[N];
int cut[N<<];
int id, maxnum = ;
void get_edge(int o, int u, int num){
sz[u] = ;
int tmp = ;
for(int i = e[].head[u]; ~i; i = e[].nt[i]){
int v = e[].to[i];
if(v == o || cut[i>>]) continue;
get_edge(u, v, num);
sz[u] += sz[v];
tmp = max(num-sz[v], sz[v]);
if(tmp < maxnum){
id = i;
maxnum = tmp;
}
}
return ;
}
int k = , op;
void dfs(int o, int u, int w){
sz[u] = ;
if(white[u]){
pq[k][op].push(pll(w, u));
if(op == ) vc[u].push_back(pll(-k, w));
else vc[u].push_back(pll(k, w));
}
for(int i = e[].head[u]; ~i; i = e[].nt[i]){
int v = e[].to[i];
if(v == o || cut[i>>]) continue;
dfs(u, v, w+e[].ct[i]);
sz[u] += sz[v];
}
return ;
}
int ans[N], lch[N], rch[N];
void update(int k){
while(!pq[k][].empty() && !white[pq[k][].top().se]) pq[k][].pop();
while(!pq[k][].empty() && !white[pq[k][].top().se]) pq[k][].pop();
if(pq[k][].empty() || pq[k][].empty())
ans[k] = ;
else {
int val1 = pq[k][].top().fi, val2 = pq[k][].top().fi;
int sum = val1 + val2 + wedge[k];
ans[k] = max(sum, );
}
if(lch[k]) ans[k] = max(ans[k], ans[lch[k]]);
if(rch[k]) ans[k] = max(ans[k], ans[rch[k]]);
return ;
}
int solve(int u, int num){
if(num == ) return ;
maxnum = inf;
get_edge(, u, num);
int now = ++k, nid = id;
cut[nid >> ] = ;
wedge[k] = e[].ct[nid];
op = ;
dfs(, e[].to[nid], );
op = ;
dfs(, e[].to[nid^], );
lch[now] = solve(e[].to[nid], sz[e[].to[nid]]);
rch[now] = solve(e[].to[nid^], sz[e[].to[nid^]]);
update(now);
return now;
}
void setWhite(int u){
for(int i = vc[u].size()-; i >= ; --i){
pll tmp = vc[u][i];
int k = tmp.fi, ct = tmp.se;
if(k < ) pq[-k][].push(pll(ct, u));
else pq[k][].push(pll(ct, u));
update(abs(k));
}
return ;
}
void setBlack(int u){
for(int i = vc[u].size()-; i >= ; --i)
update(abs(vc[u][i].fi));
return ;
}
int main(){
scanf("%d", &n);
int white_num = n, q;
char op[];
e[].init(); e[].init();
for(int i = ; i < n; i++){
scanf("%d%d%d", &u, &v, &w);
e[].add(u, v, w);
e[].add(v, u, w);
white[i] = ;
}
white[n] = ;
rebuild(, );
solve(, n);
scanf("%d", &q);
while(q--){
scanf("%s", op);
if(op[] == 'A') {
if(white_num == ) puts("They have disappeared.");
else if(white_num == ) puts("");
else printf("%d\n", ans[]);
}
else {
scanf("%d", &u);
white[u] ^= ;
if(white[u])
setWhite(u), ++white_num;
else
setBlack(u), --white_num;
}
}
return ;
}