Hide 捉迷藏 题解：裸的线段树维护树直径，但是你同时可以学到树直径和RMQ求LCA,这道题还是不错的。 现学一下这个求lca的方法： 设dp[i][j] 代表从第i个数开始连续2^j个数中的最值。 转移： dp[i][j] = max/min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 就是将区间等分为两段。 那么怎么用RMQ求LCA呢？ 我们一遍dfs，求出欧拉序（就是遍历每个节点的序号+回溯时的序号）具体看代码实现。然后我们求两个节点u,v的lca，只要求出u,v在欧拉序中的序号区间中的最小值就一定是lca。
#include<bits/stdc++.h> #define ll long long #define m (l+r)/2 #define ls o*2 #define rs o*2+1 using namespace std; const int maxn = 1e5+10; int L[maxn],R[maxn],dfn[maxn],rk[maxn],dep[maxn],dp[maxn*2][20],tot,cnt; vector<int>G[maxn]; void dfs(int u,int fa) { L[u] = ++cnt; dfn[u] = ++tot; rk[cnt] = u; dep[u] = dep[fa] + 1; dp[tot][0] = dep[u]; for(auto v :G[u]) { if(v==fa) continue; dfs(v,u); dp[++tot][0] = dep[u]; } R[u] = cnt; } void RMQ() { for(int i=1;(1<<i)<=tot;i++) for(int j=1;j+(1<<i)-1<=tot;j++) dp[j][i] = min(dp[j][i-1],dp[j+(1<<(i-1))][i-1]); } int LCA(int x,int y) { int l = dfn[x] , r = dfn[y]; if(l>r) swap(l,r); int k =log2(r-l+1); return min(dp[l][k],dp[r-(1<<k)+1][k]); } ll dist(int x,int y) { int lca = LCA(x,y); return dep[x]+dep[y]-2*lca; } struct node { int x,y; ll len; node operator+(const node&t)const { node tmp=t; if(x==0) return t; if(t.x==0) return node{x,y,len}; if(len>t.len) tmp = node{x,y,len}; ll dist1 = dist(x,t.x); ll dist2 = dist(x,t.y); ll dist3 = dist(y,t.x); ll dist4 = dist(y,t.y); if(dist1>tmp.len) tmp = node{x,t.x,dist1}; if(dist2>tmp.len) tmp = node{x,t.y,dist2}; if(dist3>tmp.len) tmp = node{y,t.x,dist3}; if(dist4>tmp.len) tmp = node{y,t.y,dist4}; return tmp; } }tr[maxn*4]; void build(int o,int l,int r) { if(l==r) { tr[o] = node{rk[l],rk[l],-1}; return ; } build(ls,l,m); build(rs,m+1,r); tr[o] = tr[ls] + tr[rs]; } void up(int o,int l,int r,int k) { if(l==r) { if(tr[o].x) tr[o] = node{0,0,-1}; else tr[o] = node{rk[l],rk[l],-1}; return ; } if(k>m) up(rs,m+1,r,k); else up(ls,l,m,k); tr[o] = tr[ls] + tr[rs]; } int main() { int n,q,u,v; char op; scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } scanf("%d",&q); dfs(1,0); RMQ(); build(1,1,n); while(q--) { getchar(); scanf("%c",&op); if(op=='G') { if(!tr[1].x) puts("-1"); else printf("%lld\n",tr[1].len); } else { scanf("%d",&u); up(1,1,n,L[u]); } } }