傳送門

如果沒有修改顯然就直接點分治

有修改那就動態點分治

動態點分治就是在點分樹上維護一些東西，查詢時也在點分樹上查

因為點分樹深度是$log$的所以可以保證時間復雜度

此題我們需要在點分樹上維護 $c$ 和 $f$

$f[x]$ 維護節點 $x$ 的子樹中傳給它父親 $Fa$ 的所有路徑長度

$c[x]$ 維護節點 $x$ 的每一個兒子 $v$ 的 $f[v]$ 的最大值

那么詢問的答案就是 max（每個節點的 $c[x]$ 的最大值與次大值之和）

那么對于維護每一個 $c[x]$ ，我們枚舉 $x$ 的所有兒子 $v$，然后把每個 $f[v]$ 的最大值加入到 $c[x]$

至于維護 $f[x]$ 就是點分治的基本操作了

對于每一個修改操作，我們要把點分樹上一條鏈的數據都進行修改，具體來說

如果是關燈，那么對于點 $x$ 這條鏈往上的每一個節點 $now$，要往 $f[now]$ 里插入一個 $dis[x][\ dep[now]\ ]$

（$dep$存每個節點的深度，$dis[x][i]$ 表示節點 $x$ 這條鏈上深度為 $i$ 的點與 $x$ 的距離）

反之如果是開燈就要刪除相應的距離

修改 $f$ 后相應的 $c$ 也要改變

實現 $f,c$ 的數據結構需要查詢最大值，次大值和支持刪除，容易想到用平衡樹或者 $multiset$ 來維護

但是題解里有一種更騷的"數據結構"，維護兩個大根堆 $hp$ 和 $rub$，分別存值和刪除的數

查詢最大值和次大值就直接在 $hp$ 里面查，刪除數的話就把要刪除的數加到 $rub$ 里面

在 $hp$ 里取出堆頂的值時如果第一個數和 $rub$ 里的第一個數相同就把兩個堆的堆頂同時彈掉直到出現不同或有一個堆空了

正確性十分的顯然，如果數 $val$ 有被刪除（即加入了 $rub$ 里），并且處在 $hp$ 的堆頂，那么 $val$ 也一定在 $rub$ 的堆頂（因為 $rub$ 里的數顯然是 $hp$ 的子集）

全局的答案也直接用這個數據結構來維護就好了

代碼有注釋

?

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> using namespace std; typedef long long ll; inline int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }return x*f; } const int N=2e5+7,INF=1e9+7; int fir[N],from[N<<1],to[N<<1],cntt; inline void add(int &a,int &b) {from[++cntt]=fir[a]; fir[a]=cntt;to[cntt]=b; } struct Heap {//c和f的數據結構priority_queue <int> hp,rub;inline void ins(int x) { hp.push(x); } //插入inline void del(int x) { hp.top()==x ? hp.pop() : rub.push(x); }//刪除inline int fir()//求最大值 {while(!hp.empty()&&!rub.empty()&&hp.top()==rub.top()) hp.pop(),rub.pop();return hp.empty() ? -INF : hp.top();//注意判斷堆是否為空 }inline int sec()//求次大值 {int t=fir(),res; if(t==-INF) return t;hp.pop(); res=fir(); hp.push(t);return res;} }Ans,c[N],f[N];//Ans維護全局的答案 int n,m,tot,rt,cnt; int sz[N],mx[N]; bool vis[N],p[N];//p是房間狀態 void find_rt(int x,int fa)//找重心 {sz[x]=1; mx[x]=0;for(int i=fir[x];i;i=from[i]){int &v=to[i]; if(vis[v]||v==fa) continue;find_rt(v,x); sz[x]+=sz[v];mx[x]=max(mx[x],sz[v]);}mx[x]=max(mx[x],tot-sz[x]);if(mx[x]<mx[rt]) rt=x; } int Fa[N],dis[N][21],dep[N],ans[N];//Fa是點分樹上的父親,ans[x]是點x的答案，用來維護Ans int st[N],Top,Dep;//當前深度 void dfs(int x,int fa) {st[++Top]=x; dis[x][Dep]=dis[fa][Dep]+1;//維護disfor(int i=fir[x];i;i=from[i]){int &v=to[i]; if(v==fa||vis[v]) continue;dfs(v,x);} } void build(int x)//建樹順便預處理初始c,f {vis[x]=1; dep[x]=dep[Fa[x]]+1;//維護點分樹的depfor(int i=fir[x];i;i=from[i]){int &v=to[i]; if(vis[v]) continue;tot=sz[v]; rt=0; find_rt(v,0);Dep=dep[x]+1; Top=0; dfs(v,0);//dfs從v開始for(int j=1;j<=Top;j++) f[rt].ins(dis[st[j]][Dep]);//把子樹的每個距離插入f[rt]c[x].ins(f[rt].fir());//用點分樹兒子更新當前節點 Fa[rt]=x; build(rt);//繼續向下建樹 }c[x].ins(0);/*別忘了插一個0,本身到自己的距離也算*/ Ans.ins( ans[x]=c[x].fir()+c[x].sec() );//維護Ans并更新ans[x] } inline void change(int x)//修改操作，在點分樹上維護數據 {int now=x,d,t1,t2;if(p[x]) cnt++,c[x].ins(0);//如果x為開燈，那么現在要關燈else cnt--,c[x].del(0);//反之要開燈while(1){t1=c[now].fir()+c[now].sec();if(t1!=ans[now]) Ans.del(ans[now]),Ans.ins(ans[now]=t1);//用c[now]更新Ans和ans[now]if(!Fa[now]) break;d=dep[now]; t1=f[now].fir();p[x] ? f[now].ins(dis[x][d]) : f[now].del(dis[x][d]);//根據房間的狀態判斷是插入還是刪除t2=f[now].fir();if(t1!=t2) c[Fa[now]].del(t1),c[Fa[now]].ins(t2);//如果狀態有更新就用f[now]更新c[Fa[now]]now=Fa[now];//往父親跳 }p[x]^=1;//改變房間狀態 } int main() {int a,b; char ch[5];cnt=n=read();for(int i=1;i<n;i++){a=read(),b=read();add(a,b); add(b,a);}tot=n; mx[0]=INF;find_rt(1,0); build(rt);m=read();while(m--){scanf("%s",ch);if(ch[0]=='G'){if(cnt==1) printf("0\n");else if(cnt==0) printf("-1\n");else printf("%d\n",Ans.fir());}else change(read());}return 0; }

?

轉載于:https://www.cnblogs.com/LLTYYC/p/10333850.html

總結

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

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