bzoj 1095
首先仍然是點對之間的問題，讓我們考慮點分
由于帶修改，所以考慮動態點分治
所謂動態點分治，就是在操作之前先模擬一遍點分治的過程構造出一棵新的樹，我們稱這棵樹為點分樹，由于這棵樹樹高是對數級別的，所以修改的時候可以在一條樹鏈上暴力修改
然后考慮本題怎么維護：
首先我們考慮答案如何統計：在統計答案時，我們找出每個節點向其所有子樹中最大的距離，然后計算這些最大深度的最大值+次大值，然后放進一個堆里維護即可
為什么要放進堆里維護？
因為還可能需要插入或刪除嘛！
這樣的話，我們考慮怎么維護答案
首先我們需要記錄以一個點為根節點的子樹中到這個點最深的深度，這一點比較好維護
然后我們還需要記錄以一個點為根節點子樹中向上更新的最深的深度，這一點也比較容易維護
（注意我們現在的樹是點分樹，但深度討論的是原來的樹！因此不能簡單地傳遞！）
接下來就是堆的刪除和修改了
有個小trick：開兩個堆，如果需要刪除的話推到另一個堆里，在查詢時如果兩堆堆頂相等就一起彈掉
需要卡常，求LCA不妨用歐拉序
貼代碼：
// luogu-judger-enable-o2 #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> #define uint unsigned int using namespace std; struct Edge { uint nxt; uint to; }edge[200005]; struct Heap { priority_queue <uint> Q1,Q2; void push(uint x){Q1.push(x);} void del(uint x){Q2.push(x);} uint top() { while(!Q1.empty()&&!Q2.empty()&&Q1.top()==Q2.top())Q1.pop(),Q2.pop(); if(!Q1.empty())return Q1.top(); else return -1; } void pop() { while(!Q1.empty()&&!Q2.empty()&&Q1.top()==Q2.top())Q1.pop(),Q2.pop(); if(!Q1.empty())Q1.pop(); } bool empty(){return Q1.size()-Q2.size()==0;} uint size(){return Q1.size()-Q2.size();} uint sec() { if(Q1.size()-Q2.size()<=1)return -1; uint t=top();pop(); uint ret=top();push(t); return ret; } }Q[100005][2],re; uint head[100005]; uint siz[100005],maxp[100005]; uint pre[100005],vis[100005]; uint sit[100005]; uint ttop[100005]; uint lg2[500005]; uint dep[100005]; uint dfn[100005]; uint rmq[500005][22]; uint s,rt; uint t=0; uint cnt=1; uint n,m,s_lig; inline void add(uint l,uint r) { edge[cnt].nxt=head[l]; edge[cnt].to=r; head[l]=cnt++; } void dfs(uint x,uint fx) { dep[x]=dep[fx]+1,dfn[x]=++t; rmq[t][0]=x; for(register uint i=head[x];i;i=edge[i].nxt) { uint to=edge[i].to; if(to==fx)continue; dfs(to,x); rmq[++t][0]=x; } } /*void redfs(uint x,uint topx,uint fx) { ttop[x]=topx; if(son[x])redfs(son[x],topx,x); for(register uint i=head[x];i;i=edge[i].nxt) { uint to=edge[i].to; if(to==fx||to==son[x])continue; redfs(to,to,x); } }*/ void get_f() { for(register uint j=1;j<=17;++j) { for(register uint i=1;i+(1<<j)-1<=t;++i) { rmq[i][j]=dep[rmq[i][j-1]]<dep[rmq[i+(1<<(j-1))][j-1]]?rmq[i][j-1]:rmq[i+(1<<(j-1))][j-1]; } } for(register uint i=2;i<=t;i++)lg2[i]=lg2[i>>1]+1; } inline uint LCA(uint x,uint y) { int l=dfn[x],r=dfn[y]; if(l>r)swap(l,r); int lg=lg2[r-l+1]; return dep[rmq[l][lg]]<dep[rmq[r-(1<<lg)+1][lg]]?rmq[l][lg]:rmq[r-(1<<lg)+1][lg]; } inline uint get_dis(uint x,uint y) { return dep[x]+dep[y]-2*dep[LCA(x,y)]; } void get_rt(uint x,uint fx) { siz[x]=1,maxp[x]=0; for(register uint i=head[x];i;i=edge[i].nxt) { uint to=edge[i].to; if(to==fx||vis[to])continue; get_rt(to,x); siz[x]+=siz[to]; maxp[x]=max(maxp[x],siz[to]); } maxp[x]=max(maxp[x],s-siz[x]); if(maxp[x]<maxp[rt])rt=x; } void solve(uint x) { vis[x]=1; for(register uint i=head[x];i;i=edge[i].nxt) { int to=edge[i].to; if(vis[to])continue; s=siz[to],rt=0; get_rt(to,0); pre[rt]=x,solve(rt); } } void ins(uint x) { if(Q[x][1].size()>=2)re.push(Q[x][1].top()+Q[x][1].sec()); } void del(uint x) { if(Q[x][1].size()>=2)re.del(Q[x][1].top()+Q[x][1].sec()); } void turn_off(uint x) { del(x),Q[x][1].push(0),ins(x); s_lig--; for(uint i=x,pi=pre[x];pi;i=pi,pi=pre[i]) { del(pi); if(!Q[i][0].empty())Q[pi][1].del(Q[i][0].top()); Q[i][0].push(get_dis(x,pi)); Q[pi][1].push(Q[i][0].top()); ins(pi); } } void turn_on(uint x) { del(x),Q[x][1].del(0),ins(x); s_lig++; for(uint i=x,pi=pre[x];pi;i=pi,pi=pre[i]) { del(pi); if(!Q[i][0].empty())Q[pi][1].del(Q[i][0].top()); Q[i][0].del(get_dis(x,pi)); if(!Q[i][0].empty())Q[pi][1].push(Q[i][0].top()); ins(pi); } } inline uint read() { uint f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { n=read(); for(register uint i=1;i<n;++i) { uint x=read(),y=read(); add(x,y),add(y,x); } rt=0,s=n,maxp[0]=0x3f3f3f3f; dfs(1,1),get_f(),get_rt(1,0),solve(rt); for(register uint i=1;i<=n;++i)turn_off(i); s_lig=0; m=read(); while(m--) { char typ=getchar(); while(typ!='C'&&typ!='G')typ=getchar(); if(typ=='C') { uint x=read(); if(sit[x])turn_off(x); else turn_on(x); sit[x]^=1; }else { if(s_lig==n)printf("-1\n"); else if(s_lig==n-1)printf("0\n"); else printf("%u\n",re.top()); } } return 0; }
浙公網安備 33010602011771號