本文轉載：http://www.cnblogs.com/YoungNeal/p/8530398.html

題目大意：

給定一棵樹，有 n-1 條樹邊，m 條非樹邊，有兩次割邊的機會，第一次只能割樹邊，第二次只能割非樹邊，問有多少種方案使得兩次之后樹分為兩個部分？

題解： 我們稱每條非樹邊 (x,y) 都把樹上 x,y 之間的路徑上的每條邊“覆蓋了一次”。我們只需統計出每條樹邊被覆蓋了次數。若第一步把覆蓋 0 次的樹邊切斷，則第二步可以任意切斷一條非樹邊。若第一步把被覆蓋 1 次的樹邊切斷，則第二次方法唯一。若第一步把被覆蓋 2 次及以上的樹邊切斷，那么第二步無解。

所以我們接下來要解決的問題模型是：給定一張無向圖和一顆生成樹，求每條“樹邊”被“非樹邊”覆蓋了多少次。

解決此問題有一個經典做法，我們稱之為“樹上差分算法”。我們給每個節點一個初始為 0 的權值，然后對每條非樹邊 (x,y) ,令節點 x 的權值加 1，節點 y 的權值加 1，節點 LCA(x,y) 的權值減 2。最后對這棵生成樹進行一次深度優先遍歷，求出 F[x] 表示以 x 為根的子樹中各節點權值的和。F[x] 就是 x 與它的父節點之間的“樹邊”被覆蓋的次數。時間復雜度 O(N+M)。

　　　　　　　　　　　　　　　　　　　　　--《算法競賽進階指南》 注意最后求 ans 時，要從 2 開始，因為 1 的權值一定為 0。

（求樹上路徑被覆蓋次數都可以采用樹上差分）

代碼：

#include<cstdio> #include<cstring> #define N 100005 #define int long long using namespace std;bool vis[N]; int head[N]; int cf[N],q[N]; int n,m,cnt,ans; int d[N],f[N][30];struct Edge{int to,nxt; }edge[N<<1];void add(int x,int y){edge[++cnt].to=y;edge[cnt].nxt=head[x];head[x]=cnt; }void dfs(int now){for(int i=head[now];i;i=edge[i].nxt){int to=edge[i].to;if(d[to]) continue;d[to]=d[now]+1;f[to][0]=now;for(int k=1;k<=21;k++)f[to][k]=f[f[to][k-1]][k-1];dfs(to);} }int lca(int x,int y){if(d[x]<d[y]) x^=y^=x^=y;for(int k=21;~k;k--){if(d[f[x][k]]>=d[y]) x=f[x][k];}if(x==y) return y;for(int k=21;~k;k--){if(f[x][k]!=f[y][k])x=f[x][k],y=f[y][k];}return f[x][0]; }void dfs2(int now){vis[now]=1;for(int i=head[now];i;i=edge[i].nxt){int to=edge[i].to;if(!vis[to]){dfs2(to);cf[now]+=cf[to];}} }signed main(){scanf("%lld%lld",&n,&m);for(int x,y,i=1;i<n;i++){scanf("%lld%lld",&x,&y);add(x,y);add(y,x);}d[1]=1;dfs(1);for(int x,y,i=1;i<=m;i++){scanf("%lld%lld",&x,&y);cf[x]++,cf[y]++;cf[lca(x,y)]-=2;}dfs2(1);for(int i=2;i<=n;i++){if(cf[i]==0) ans+=m;if(cf[i]==1) ans++;}printf("%lld",ans);return 0; }

?

?

轉載于:https://www.cnblogs.com/Miracevin/p/9031509.html

總結

以上是生活随笔為你收集整理的POJ 3417 Network的全部內容，希望文章能夠幫你解決所遇到的問題。

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