C138 线段树分治 P2056 [ZJOI2007] 捉迷藏

视频链接：C138 线段树分治 P2056 [ZJOI2007] 捉迷藏_哔哩哔哩_bilibili

 

 

 

P2056 [ZJOI2007] 捉迷藏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 线段树分治 O(nlognlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
const int N=500005;
int n,q;
int head[N],ne[N<<1],to[N<<1],idx;
void add(int u,int v){to[++idx]=v;ne[idx]=head[u];head[u]=idx;
}
int fa[N],son[N],dep[N],siz[N],top[N];void dfs1(int u,int f){ //搞fa,son,depfa[u]=f;siz[u]=1;dep[u]=dep[f]+1;for(int i=head[u];i;i=ne[i]){int v=to[i];if(v==f) continue;dfs1(v,u);siz[u]+=siz[v];if(siz[son[u]]<siz[v])son[u]=v;}
}
void dfs2(int u,int t){ //搞toptop[u]=t;  //记录链头if(son[u])dfs2(son[u],t);//搜重儿子for(int i=head[u];i;i=ne[i]){int v=to[i];if(v==fa[u]||v==son[u])continue;dfs2(v,v); //搜轻儿子
  }
}
int lca(int u,int v){while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]])swap(u,v);u=fa[top[u]];}return dep[u]<dep[v]?u:v;
}int lst[N];    //上次出现的时刻
bitset<N> col; //黑色=0
bitset<N> qb;  //查询=1
vector<int> tr[N<<2];   //节点
stack<pair<int,int>>st; //栈
int u,v,ans[N];void insert(int i,int l,int r,int L,int R,int x){if(L>r||R<l) return;if(L<=l&&r<=R) return tr[i].push_back(x);insert(ls,l,mid,L,R,x);insert(rs,mid+1,r,L,R,x);
}
int dis(int x,int y){ //两点距离return dep[x]+dep[y]-2*dep[lca(x,y)];
}
void solve(int i,int l,int r){auto now=st.size();for(int x:tr[i]){st.push({u,v}); //旧直径入栈if(!u&&!v) u=x,v=x;else{int d0=dis(u,v),d1=dis(u,x),d2=dis(v,x);int d=max(d0,max(d1,d2));if(d1==d) v=x;else if(d2==d) u=x; //更新直径端点
    }}if(l==r) ans[l]=(!u||!v)?-1:dis(u,v);else solve(ls,l,mid),solve(rs,mid+1,r);while(st.size()!=now){ //撤销auto t=st.top();u=t.first,v=t.second;st.pop();}
}
int main(){ios::sync_with_stdio(false);cin>>n;for(int i=1,u,v;i<n;i++){cin>>u>>v; add(u,v);add(v,u);}dfs1(1,0);dfs2(1,0); //树链剖分for(int i=1;i<=n;i++) lst[i]=1;cin>>q;for(int i=1,x;i<=q;i++){ //操作为时间轴char c; cin>>c;if(c=='C'){cin>>x;if(!col[x]){ //黑色=0col[x]=1;insert(1,1,q,lst[x],i,x); //插入x的出现时间
      }else col[x]=0,lst[x]=i; //记录x再次出现时刻
    }else qb[i]=1; //i时刻是查询
  }for(int i=1;i<=n;i++) //插入i的出现时间if(!col[i]) insert(1,1,q,lst[i],q,i);solve(1,1,q);for(int i=1;i<=q;i++)if(qb[i])printf("%d\n",ans[i]);
}