解析

見到動態維護最遠點對，不難想到利用 set 維護最大值和次大值，每個點維護兩個 set 的雜技做法。
但是問題是…T了啊。
咋辦嘞。

一個在本題至關重要的 trick：利用兩個堆來支持訪問最大值和刪除
具體也很好理解：當刪除的時候，就向第二個堆 push 一個刪除元素，每次訪問的時候先把原堆和刪除堆堆頂一樣的元素彈掉即可。
支持了刪除，剩下的就簡單了。

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define OK printf("ok\n") #define debug(...) fprintf(stderr,__VA_ARGS__) inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } const int N=2e5+100; const int inf=1e9+100; int n,m; struct node{int to,nxt; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt;return; } int dep[N],q[N<<1],tot,pl[N]; void dfs0(int x,int f){dep[x]=dep[f]+1;q[++tot]=x;pl[x]=tot;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f) continue;dfs0(to,x);q[++tot]=x;}return; } int Min(int x,int y){return dep[x]<dep[y]?x:y; } int lg[N<<1],mn[N<<1][20],mi[20]; void init(){dfs0(1,0);lg[0]=-1;for(int i=1;i<=tot;i++) lg[i]=lg[i>>1]+1;mi[0]=1;for(int i=1;i<=lg[tot];i++) mi[i]=mi[i-1]<<1;for(int i=1;i<=tot;i++) mn[i][0]=q[i];for(int k=1;k<=lg[tot];k++){for(int i=1;i+mi[k]-1<=tot;i++) mn[i][k]=Min(mn[i][k-1],mn[i+mi[k-1]][k-1]);}return; } inline int Lca(int x,int y){x=pl[x];y=pl[y];if(x>y) swap(x,y);int k=lg[y-x+1];//printf(" k=%d\n",k);return Min(mn[x][k],mn[y-mi[k]+1][k]); } inline int Dis(int x,int y){int lca=Lca(x,y);//printf("(%d %d) lca=%d dis=%d\n",x,y,lca,dep[x]+dep[y]-2*dep[lca]);return dep[x]+dep[y]-2*dep[lca]; } vector<int>f[2][N]; int w[N],top[N]; int rt,mnn,siz[N],S,son[N]; bool vis[N]; int o; void findrt(int x,int f){siz[x]=1;son[x]=0;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f||vis[to]) continue;findrt(to,x);siz[x]+=siz[to];son[x]=max(son[x],siz[to]);}son[x]=max(son[x],S-siz[x]);if(mnn>son[x]){mnn=son[x];rt=x;}return; } int tim; int solve(int x,int nS){//if(tim%1000==0) debug("%d\n",x);//printf("??\n");S=nS;mnn=inf;findrt(x,0);x=rt;vis[x]=1;siz[x]=nS+1;f[0][x].resize(siz[x]+1);f[1][x].resize(siz[x]+1);for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(vis[to]) continue;int tmp=solve(to,nS-son[to]);top[tmp]=x;}return x; } struct Set{priority_queue<int>q,d;inline bool empty(){return q.size()==d.size();}inline int size(){return q.size()-d.size();}inline void upd(){while(!d.empty()&&q.top()==d.top()) q.pop(),d.pop();}inline int top(){ upd();return q.top();}inline void del(int x){d.push(x);return;}inline void pop(){upd();q.pop();} inline void ins(int x){q.push(x);return;}inline int sec(){upd();int x=top();pop();int y=top();ins(x);return y;} }; Set s0[N],s1[N],ans; inline int calc(int x){return s0[x].top()+s0[x].sec(); } void ins(int x,int w){if(s0[x].size()>=2) ans.del(calc(x));s0[x].ins(w);if(s0[x].size()>=2) ans.ins(calc(x));return; } void era(int x,int w){if(s0[x].size()>=2) ans.del(calc(x));s0[x].del(w);if(s0[x].size()>=2) ans.ins(calc(x));return; } int op[N],num; void add(int x){++num;//printf("\nadd:%d\n",x);ins(x,0);for(int i=x;top[i];i=top[i]){if(!s1[i].empty()) era(top[i],s1[i].top());s1[i].ins(Dis(x,top[i]));ins(top[i],s1[i].top());}return; } void del(int x){--num;era(x,0);for(int i=x;top[i];i=top[i]){era(top[i],s1[i].top());s1[i].del(Dis(x,top[i]));if(!s1[i].empty()) ins(top[i],s1[i].top());}return; } signed main(){ #ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout); #endifmemset(fi,-1,sizeof(fi));cnt=-1;n=read();for(int i=1;i<n;i++){int x=read(),y=read();addline(x,y);addline(y,x);}init(); solve(1,n);//for(int i=1;i<=n;i++) printf("i=%d top=%d\n",i,top[i]);for(int i=1;i<=n;i++) add(i);m=read();char c;for(int i=1;i<=m;i++){scanf(" %c",&c);if(c=='G'){if(!ans.empty()) printf("%d\n",ans.top());else if(num) printf("0\n");else printf("-1\n");}else{int x=read();if(op[x]) add(x);else del(x);op[x]^=1;}}return 0; } /* */

總結

以上是生活随笔為你收集整理的洛谷P2056：[ZJOI2007]捉迷藏（点分树、STL）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。