视频链接: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,dep fa[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){ //搞top top[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]){ //黑色=0 col[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]); }
标签:int,C138,捉迷藏,P2056,ZJOI2007,include,col From: https://www.cnblogs.com/dx123/p/18239898