传送门
闲着无聊打算用链分治写一遍，结果因为脑瓜子不好用调了两个多小时。。。
其实是第一次自己打链分治
用
维护轻儿子向下的最长链
考虑最后的路径一定经过某一条重链（或是一个点）
让这条路径在这条路径在这个重链上统计
维护向上的最长链和向下的最长链然后拼接，跟最大子段和差不多
#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
cs int N = 1e5 + 5;
cs int INF = 1e9;
int fix(int x){ if(x-223206<-INF) x=-INF; return x;}
int read(){int cnt = 0, f = 1; char ch = 0;while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; }while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();return cnt * f;
}
int n, m, ct, col[N];
vector<int> v[N];
int sz[N],son[N],dep[N],fa[N],top[N],bot[N],in[N],ps[N],sign;
multiset<int> S[N], Ans;
typedef multiset<int>::iterator It;
void pre_dfs(int u, int f){sz[u]=1;for(auto t:v[u]) if(t^f){dep[t]=dep[u]+1; fa[t]=u; pre_dfs(t,u); sz[u] += sz[t];if(sz[t]>sz[son[u]]) son[u]=t;}
}
void dfs(int u, int tp){top[u]=tp; in[u]=++sign; ps[sign]=u; if(son[u]) dfs(son[u],tp),bot[u]=bot[son[u]];else bot[u]=u, Ans.insert(-INF);for(auto t:v[u]) if((t^fa[u])&&(t^son[u])) dfs(t,t), S[u].insert(-INF);
}
struct data{ int lv,rv,mx,sm; };
data operator + (data a, data b){return (data){fix(max(a.lv,a.sm+b.lv)), fix(max(b.rv,b.sm+a.rv)),fix(max(max(a.mx,b.mx),a.rv+b.lv)), a.sm+b.sm};
}
namespace SGT{cs int N = ::N<<2;data t[N]; #define mid ((l+r)>>1)void pushup(int x){ t[x]=t[x<<1]+t[x<<1|1]; }void build(int x, int l, int r){t[x].lv = t[x].rv = t[x].mx = -INF; t[x].sm = r-l+1;if(l == r) return; build(x<<1,l,mid); build(x<<1|1,mid+1,r);}void upt(int x, int l, int r, int p){if(l == r){t[x].lv = t[x].rv = t[x].mx = -INF;p = ps[p]; It it = S[p].end();if(S[p].size() >= 1) t[x].lv = t[x].rv = fix((*--it)+1);if(S[p].size() >= 2) t[x].mx = fix(t[x].lv + (*--it));return;} if(p<=mid) upt(x<<1,l,mid,p);else upt(x<<1|1,mid+1,r,p); pushup(x);}data query(int x, int l, int r, int L, int R){if(L<=l && r<=R) return t[x]; if(R<=mid) return query(x<<1,l,mid,L,R);else if(L>mid) return query(x<<1|1,mid+1,r,L,R);else return query(x<<1,l,mid,L,R)+query(x<<1|1,mid+1,r,L,R);}
}
void modify(int x, int op){bool FLAG = true; int vl = SGT::query(1,1,n,in[top[x]],in[bot[x]]).lv;while(x){int tp = fa[top[x]];if(tp){data nx = SGT::query(1,1,n,in[top[tp]],in[bot[tp]]);Ans.erase(Ans.find(nx.mx)); S[tp].erase(S[tp].find(vl)); vl=nx.lv;}if(FLAG){Ans.erase(Ans.find(SGT::query(1,1,n,in[top[x]],in[bot[x]]).mx));if(op == 1) S[x].insert(0); else S[x].erase(S[x].find(0));SGT::upt(1,1,n,in[x]); Ans.insert(SGT::query(1,1,n,in[top[x]],in[bot[x]]).mx);FLAG = false;}if(tp){S[tp].insert(SGT::query(1,1,n,in[top[x]],in[bot[x]]).lv);SGT::upt(1,1,n,in[tp]); Ans.insert(SGT::query(1,1,n,in[top[tp]],in[bot[tp]]).mx);} x = tp;}
}
int main(){n = ct = read();for(int i = 1; i < n; i++){int x = read(), y = read();v[x].pb(y); v[y].pb(x);} pre_dfs(1,0); dfs(1,1); SGT::build(1,1,n);for(int i = 1; i <= n; i++) modify(i,1);m = read();while(m--){char op[2]; scanf("%s", op);if(op[0] == 'G'){if(ct == 0) puts("-1");else if(ct == 1) puts("0");else cout << *(--Ans.end())-1 << '\n';}if(op[0] == 'C'){int x = read(); if(col[x]==0) modify(x,-1); else modify(x,1); col[x]^=1;}} return 0;
}