題目：http://acm.hdu.edu.cn/showproblem.php?pid=5511

題意：割一些邊使得無向圖變成不連通的，并且恰好割了兩條給定生成樹上的邊。滿足非樹邊兩段一定在給定生成樹的根的不同子樹里。求最小邊數。

看了題解。

　　一直考慮割出來的是樹上的連通塊之類的。

　　其實考慮討論那兩條樹邊的關系。

　　1.兩條邊是祖先--后代關系。

　　　　答案就是它們之間夾著的連通塊伸出去的非樹邊條數+2。所以兩條邊離得越近越好。

　　　　那么就是一個點的父親邊+該點父親的父親邊。O(n)枚舉即可。

　　　　注意1號點沒有父親邊。

　　2.兩條邊不是祖先--后代關系。

　　　　那么兩條邊引導了兩個子樹。答案就是這兩個子樹伸出去的非樹邊條數 - 兩個子樹相互的非樹邊條數*2 + 2 。

　　　　然后又不太會了。

　　　　其實考慮答案形如 d[ x ] + d[ y ] - 2*cnt( x, y ) ，那么枚舉 x ，用線段樹維護 d[ y ] - 2*cnt( x, y ) 的最小值即可。注意1號點不能參與。

　　　　那么就是線段樹合并得到 cnt( ) ，再加入當前根 cr 的貢獻，就是 cr 連出去的點 y ， y 到父親的鏈上的值都 - 2 。

　　　　還要把 cr 的位置設成 INF 。

　　動態開點。每個點的初值是 “只考慮 d[ ] 不考慮 cnt ，區間最小值” 。這個可以預處理。借鑒了 Claris 的寫法，把該值記在以 cr << 1 , cr<<1|1 為結構得到的線段樹角標上。

　　注意如果沒有左孩子或右孩子之類的，調用的是上述初值而不是 0 或 INF 。

　　直接線段樹合并，空間不行。考慮像 dsu on tree 一樣，每個點繼承其重孩子的線段樹。線段樹合并之后，輕孩子的線段樹節點都刪掉。這樣同時又 log 個線段樹，空間可行。

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define pb push_back #define ls Ls[cr] #define rs Rs[cr] using namespace std; int rdn() {int ret=0;bool fx=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return fx?ret:-ret; } int Mx(int a,int b){return a>b?a:b;} int Mn(int a,int b){return a<b?a:b;} const int N=2e4+5,M=N*60,INF=1e6+5; int n,m,hd[N],xnt,to[N<<1],nxt[N<<1],rd[N],ans; int tim,dfn[N],dy[N],top[N],son[N],siz[N],fa[N],dep[N]; int rt[N],tot,Ls[M],Rs[M],mn[M],tg[M]; int w[N<<2],dlpl[M],dtop; vector<int> vt[N]; void init() {xnt=0; for(int i=1;i<=n;i++)hd[i]=0;tim=tot=dtop=0;for(int i=1;i<=n;i++)vector<int>().swap(vt[i]);for(int i=1;i<=n;i++)son[i]=0;/// for(int i=1;i<=n;i++)rt[i]=0;/// for(int i=1;i<=n*4;i++)w[i]=INF; } void add(int x,int y) {to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;} void ini_build(int l,int r,int cr) {if(l==r){if(dy[l]==1)w[cr]=INF;else w[cr]=rd[dy[l]];return;}int mid=l+r>>1;ini_build(l,mid,cr<<1);ini_build(mid+1,r,cr<<1|1);w[cr]=Mn(w[cr<<1],w[cr<<1|1]); } void dfs(int cr,int f) {fa[cr]=f; dep[cr]=dep[f]+1; siz[cr]=1;rd[cr]=vt[cr].size();for(int i=hd[cr],v;i;i=nxt[i])if((v=to[i])!=f){dfs(v,cr); rd[cr]+=rd[v]; siz[cr]+=siz[v];if(siz[v]>siz[son[cr]])son[cr]=v;}if(cr==1)return;// for(int i=hd[cr],v;i;i=nxt[i])if((v=to[i])!=f)ans=Mn(ans,rd[cr]-rd[v]); } void dfsx(int cr,int f) {dfn[cr]=++tim; dy[tim]=cr;if(son[cr]){ top[son[cr]]=top[cr];dfsx(son[cr],cr);}for(int i=hd[cr],v;i;i=nxt[i])if((v=to[i])!=f&&v!=son[cr]){ top[v]=v; dfsx(v,cr);} } int nwnd(int id) {int cr;if(dtop)cr=dlpl[dtop--]; else cr=++tot;ls=rs=tg[cr]=0; mn[cr]=w[id]; return cr; } void del(int x){ dlpl[++dtop]=x;} void pshp(int cr,int id)//if!!! {if(ls)mn[cr]=mn[ls]; else mn[cr]=w[id<<1];if(rs)mn[cr]=Mn(mn[cr],mn[rs]);else mn[cr]=Mn(mn[cr],w[id<<1|1]); } void pshd(int cr,int id) {if(!tg[cr])return; int w=tg[cr]; tg[cr]=0;if(!ls)ls=nwnd(id<<1); if(!rs)rs=nwnd(id<<1|1);tg[ls]+=w; tg[rs]+=w; mn[ls]+=w; mn[rs]+=w; } void mdfy(int l,int r,int &cr,int id,int p) {if(!cr)cr=nwnd(id); if(l==r){mn[cr]=INF;return;}int mid=l+r>>1; pshd(cr,id);if(p<=mid)mdfy(l,mid,ls,id<<1,p);else mdfy(mid+1,r,rs,id<<1|1,p);pshp(cr,id); } void add(int l,int r,int &cr,int id,int L,int R) {if(!cr)cr=nwnd(id);if(l>=L&&r<=R){tg[cr]-=2;mn[cr]-=2;return;}int mid=l+r>>1; pshd(cr,id);if(L<=mid)add(l,mid,ls,id<<1,L,R);if(mid<R)add(mid+1,r,rs,id<<1|1,L,R);pshp(cr,id); } void mrg(int l,int r,int &cr,int id,int v) {if(!cr){cr=v;return;} if(!v)return;if(l==r){if(mn[cr]==INF||mn[v]==INF)mn[cr]=INF;else {mn[cr]+=mn[v]; mn[cr]-=rd[dy[l]];}del(v); return;}int mid=l+r>>1; pshd(cr,id); pshd(v,id);mrg(l,mid,ls,id<<1,Ls[v]);mrg(mid+1,r,rs,id<<1|1,Rs[v]);pshp(cr,id); del(v); } void solve(int cr) {if(son[cr]){ solve(son[cr]); rt[cr]=rt[son[cr]];}for(int i=hd[cr],v;i;i=nxt[i])if((v=to[i])!=fa[cr]&&v!=son[cr]){solve(v); mrg(1,n,rt[cr],1,rt[v]);}if(cr==1)return;////!!!mdfy(1,n,rt[cr],1,dfn[cr]);for(int i=0,lm=vt[cr].size();i<lm;i++){int x=vt[cr][i];while(top[x]!=1){add(1,n,rt[cr],1,dfn[top[x]],dfn[x]);x=fa[top[x]];}if(x>1)add(1,n,rt[cr],1,2,dfn[x]);///no 1 }ans=Mn(ans,rd[cr]+mn[rt[cr]]); } int main() {int T=rdn();for(int t=1;t<=T;t++){n=rdn();m=rdn(); init();for(int i=1,u,v;i<n;i++){u=rdn();v=rdn();add(u,v);add(v,u);}for(int i=n,u,v;i<=m;i++){u=rdn();v=rdn();vt[u].pb(v); vt[v].pb(u);}ans=INF; dfs(1,0);top[1]=1; dfsx(1,0);ini_build(1,n,1); solve(1);printf("Case #%d: %d\n",t,ans+2);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/Narh/p/11073015.html

總結

以上是生活随笔為你收集整理的hdu 5511 Minimum Cut-Cut——分类讨论思想+线段树合并的全部內容，希望文章能夠幫你解決所遇到的問題。

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