正題

題目鏈接:http://www.ybtoj.com.cn/contest/122/problem/2

---

題目大意

給出$n$個點的一棵有根樹，對于每個$x$求，刪除點$x$后修改某個點的父節點（修改前該點必須有父節點）后最小化最大聯通塊大小。

---

解題思路

刪掉一個點后肯定是最大的那個聯通塊分一個子樹給最小的那個聯通塊。
設$maxs$表示最大的聯通塊，$rmax$表示次大的聯通塊，$mins$表示最小的聯通塊，那么答案一定在$[rmax,maxs]$之間，而且最小化最大值我們可以考慮二分

然后要分成兩種情況
若最大聯通塊是某一個兒子的子樹，這種情況很好處理，我們用線段樹合并計算出每個子樹可以取的子樹大小（不包括它本身），然后判斷一下是否有大小在$[maxs?mid,mid?mins]$中的子樹就好了。

若最大聯通塊是父節點所在聯通塊的子樹，這種情況比較麻煩，我們需要把點分成兩種，一種是在$x$到根節點路徑上的，一種是不在那個上面的。
用樹狀數組記錄一下在$x$到根節點路徑上的子樹大小，然后用總共的減去樹狀數組的和之前線段樹那個在$x$子樹內的就是不在到根節點路徑上的，這些和之前那樣查詢就好了。
剩下在到根路徑上的節點的子樹大小都減少了$si{z}_x$，我們將查詢的區間右移$si{z}_x$位就好了，用剛剛那個樹狀數組就好了

時間復雜度$O(n{\log }^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define lowbit(x) (x&-x) using namespace std; const int N=1e5+10; struct node{int to,next; }a[N]; int n,tot,fa[N],deg[N],ls[N],rt[N],siz[N],ans[N]; struct SegTree{int w[N<<5],ls[N<<5],rs[N<<5],cnt;int Change(int x,int L,int R,int pos){int p=++cnt;w[p]=w[x]+1;if(L==R)return p;int mid=(L+R)>>1;if(pos<=mid)ls[p]=Change(ls[x],L,mid,pos),rs[p]=rs[x];else rs[p]=Change(rs[x],mid+1,R,pos),ls[p]=ls[x];return p;}int Ask(int x,int L,int R,int l,int r){if(!x)return 0;if(L==l&&R==r)return w[x];int mid=(L+R)>>1;if(r<=mid)return Ask(ls[x],L,mid,l,r);if(l>mid)return Ask(rs[x],mid+1,R,l,r);return Ask(ls[x],L,mid,l,mid)+Ask(rs[x],mid+1,R,mid+1,r);}int Merge(int x,int y){if(!x||!y)return x+y;int p=++cnt;w[p]=w[x]+w[y];ls[p]=Merge(ls[x],ls[y]);rs[p]=Merge(rs[x],rs[y]);return p;} }T; struct TreeBinary{int t[N];void Change(int x,int val){while(x<=n){t[x]+=val;x+=lowbit(x);}return;}int Ask(int x){int ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans;} }B,D; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x){siz[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;dfs(y);siz[x]+=siz[y];rt[x]=T.Change(rt[x],1,n,siz[y]);rt[x]=T.Merge(rt[x],rt[y]);}D.Change(siz[x],1);return; } int epe(int L,int R,int x){if(L>R)return 0;return D.Ask(R)-D.Ask(L-1)+B.Ask(R+siz[x])-B.Ask(L+siz[x]-1)-T.Ask(rt[x],1,n,L,R); } void work(int x){if(x==36449)x++,x--;if(deg[x]<2){ans[x]=max(siz[1]-siz[x],siz[a[ls[x]].to]);return;}int p=0,mins=n,maxs=0,rmax=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(siz[y]>maxs)rmax=maxs,maxs=siz[y],p=y;else if(siz[y]>rmax)rmax=siz[y];mins=min(mins,siz[y]);}if(siz[1]-siz[x]>maxs){rmax=maxs;maxs=siz[1]-siz[x];mins=min(mins,siz[1]-siz[x]);int L=rmax,R=maxs-1;while(L<=R){int mid=(L+R)>>1;int l=maxs-mid,r=mid-mins;if(epe(l,r,x))R=mid-1;else L=mid+1;}ans[x]=L;return;}else if(fa[x]){if(siz[1]-siz[x]>rmax)rmax=siz[1]-siz[x];mins=min(mins,siz[1]-siz[x]);}int L=rmax,R=maxs-1;while(L<=R){int mid=(L+R)>>1;int l=maxs-mid,r=mid-mins;if(T.Ask(rt[p],1,n,l,r))R=mid-1;else L=mid+1;}ans[x]=L;return; } void calc(int x){D.Change(siz[x],-1);work(x);B.Change(siz[x],1);for(int i=ls[x];i;i=a[i].next)calc(a[i].to);B.Change(siz[x],-1);D.Change(siz[x],1); } int main() {freopen("traffic.in","r",stdin);freopen("traffic.out","w",stdout);scanf("%d",&n);for(int i=2;i<=n;i++){scanf("%d",&fa[i]);deg[fa[i]]++;deg[i]++;addl(fa[i],i);}dfs(1);D.Change(siz[1],-1);work(1);B.Change(siz[1],1);for(int i=ls[1];i;i=a[i].next)calc(a[i].to);for(int i=1;i<=n;i++)printf("%d\n",ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的YbtOJ#662-交通运输【线段树合并,树状数组】的全部內容，希望文章能夠幫你解決所遇到的問題。

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