这题有很多的做法。
首先最远的两个点很显然是直径。
然后和之前做的一道直径合并很像。
我们知道这里是一个单点修改，修改了之后会影响它的父节点以上的情况。
那么，我们又知道dfs序满足子节点的dfs序在父节点的dfs序内部。
那么我们可以用线段树去维护dfs的区间直径。
然后显然这个区间是子树的包含关系，所以显然子区间到大区间就是向父节点合并子树~。
然后树上距离合并直径。这里用了常熟优化的倍增~。
复杂度O(mlogn^2），st表的话mlogn
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<string,int> pii; const int N = 1e5+5; const int M = 2e5+5; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; int n,id[N],dep[N],vis[N],ssize[N],rk[N],f[N][25],lg[N],tot = 0; vector<int> G[N]; struct Node{int L,r,p1,p2,dis;}node[N<<2]; void init(){for(int i = 1;i < N;++i) lg[i] = lg[i-1] + ((1<<lg[i-1]) == i);} void dfs(int u,int fa) { id[u] = ++tot;rk[tot] = u; dep[u] = dep[fa]+1;f[u][0] = fa; for(rg int i = 1;i <= lg[dep[u]];++i) f[u][i] = f[f[u][i-1]][i-1]; for(auto v : G[u]) if(v != fa) dfs(v,u); } int LCA(int x,int y) { if(dep[x] < dep[y]) swap(x,y); while(dep[x] > dep[y]) x = f[x][lg[dep[x]-dep[y]]-1]; if(x == y) return x; for(rg int i = lg[dep[x]]-1;i >= 0;--i) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i]; return f[x][0]; } int Dis(int x,int y){return dep[x]+dep[y]-2*dep[LCA(x,y)];} void Pushup(int idx) { int dis = -1,p1 = 0,p2 = 0; if(node[idx<<1].p1) { if(node[idx<<1|1].p1){ int tmp = Dis(node[idx<<1].p1,node[idx<<1|1].p1); if(tmp > dis) dis = tmp,p1 = node[idx<<1].p1,p2 = node[idx<<1|1].p1; } if(node[idx<<1|1].p2){ int tmp = Dis(node[idx<<1].p1,node[idx<<1|1].p2); if(tmp > dis) dis = tmp,p1 = node[idx<<1].p1,p2 = node[idx<<1|1].p2; } } if(node[idx<<1].p2) { if(node[idx<<1|1].p1){ int tmp = Dis(node[idx<<1].p2,node[idx<<1|1].p1); if(tmp > dis) dis = tmp,p1 = node[idx<<1].p2,p2 = node[idx<<1|1].p1; } if(node[idx<<1|1].p2){ int tmp = Dis(node[idx<<1].p2,node[idx<<1|1].p2); if(tmp > dis) dis = tmp,p1 = node[idx<<1].p2,p2 = node[idx<<1|1].p2; } } if(node[idx<<1].p1 && node[idx<<1].p2 && node[idx<<1].dis > dis) dis = node[idx<<1].dis,p1 = node[idx<<1].p1,p2 = node[idx<<1].p2; if(node[idx<<1|1].p1 && node[idx<<1|1].p2 && node[idx<<1|1].dis > dis) dis = node[idx<<1|1].dis,p1 = node[idx<<1|1].p1,p2 = node[idx<<1|1].p2; if(p1 == 0) p1 = max(max(node[idx<<1].p1,node[idx<<1].p2),max(node[idx<<1|1].p1,node[idx<<1|1].p2));//只有一个元素时. node[idx].p1 = p1;node[idx].p2 = p2;node[idx].dis = dis; } void build(int L,int r,int idx) { node[idx].L = L,node[idx].r = r; if(L == r){ node[idx].p1 = rk[L]; node[idx].p2 = 0; node[idx].dis = -1; return ; } int mid = (L+r)>>1; build(L,mid,idx<<1);build(mid+1,r,idx<<1|1); Pushup(idx); } void update(int x,int idx) { if(node[idx].L == node[idx].r) { if(node[idx].p1 == 0) node[idx].p1 = rk[node[idx].L]; else node[idx].p1 = 0; return ; } int mid = (node[idx].L+node[idx].r)>>1; if(mid >= x) update(x,idx<<1); else update(x,idx<<1|1); Pushup(idx); } int main() { init(); n = read(); for(int i = 1;i < n;++i) { int x,y;x = read(),y = read(); G[x].push_back(y); G[y].push_back(x); } dfs(1,0); build(1,tot,1); int num = n; int q;q = read(); while(q--) { char c = getchar(); while(c != 'C' && c != 'G') c = getchar(); if(c == 'C') { int x;x = read(); if(!vis[x]) vis[x] = 1,num--; else vis[x] = 0,num++; update(id[x],1); } else { if(num == 0) printf("-1 "); else if(num == 1) printf("0 "); else printf("%d ",node[1].dis); } } }