題目鏈接：點擊查看

題目大意：（摘自大藍書）Dark是人類內心的黑暗的產物，古今中外的勇者們都試圖打倒它。經過研究，你發現Dark呈現無向圖的結構，圖中有N個節點和兩類邊，一類邊被稱為主要邊，而另一類被稱為附加邊。Dark有N-1條主要邊，并且Dark的任意兩個節點之間都存在一條只由主要邊構成的路徑。另外，Dark還有M條附加邊。

你的任務是把Dark斬為不連通的兩部分。一開始Dark的附加邊都處于無敵狀態，你只能選擇一條主要邊切斷。一旦你切斷了一條主要邊，Dark就會進入防御模式，主要邊會變為無敵的狀態，而附加邊可以被切斷。但是你的能力只能再切斷Dark的一條附加邊。現在你想要知道，一共有多少種方案可以擊敗Dark。注意，就算你第一步切斷主要邊之后就已經把Dark斬為兩截，你也需要切斷一條附加邊才算擊敗了Dark。

N<=1e5,M<=1e5,數據保證答案不超過2^31-1

題目分析：本來是想學網絡流的，順手翻到了這個題，感覺和前兩天做過的那道題很像，就拿來做了做，發現真的是大同小異的一個題目，之前那個樹上差分的題目求的是最小去掉幾條邊才能讓整棵樹分成兩個部分，這個題目只讓去掉兩條邊，一條樹上的邊，一條樹外的邊，問有多少種方案能將整棵樹分為兩半，因為題目也提示了，第一步切斷樹內的邊后也是還需要再切斷一條樹外的邊才算擊敗，那么我們可以分類討論一下，假設現在我們已經求出所有附加邊對主要邊的貢獻為sum[i]了：

若sum[i]==0，說明切斷當前邊i，即可讓整棵樹分為兩部分，那么我們只需要再隨意切斷一條邊就可以擊敗Dark，所以總貢獻為m

若sum[i]==1，說明切斷當前邊i后，還需要切斷給sum[i]提供貢獻的那條附加邊，所以情況是唯一的，此時貢獻為1

若sum[i]>=2，說明切斷當前邊i后，只切斷一條附加邊是無法滿足條件的，所以此時的貢獻為0

按照上面的情況，分類討論加權答案即可

上代碼之前不得不吐槽兩句，我是真的佛了，poj的評測機到底什么時候才能支持C++11？對于我這個懶癌患者極度不友好，先不說stl里的無序map和雙端隊列用不了，連auto也用不了，我干脆用vc++6.0編代碼陪你一起回到上個世紀好不好

限制那么多也就算了，題意不明，你不說明白，鬼知道你默認的是多組輸入？

這個題我是十一點半寫完的，交上去第一發編譯錯誤，第二發編譯錯誤，第三發超時，我就想應該是鄰接表太慢了，換了一發鏈式前向星，然后，poj就崩了。。崩了半小時交上去WA了，把代碼拿下來換上了多組輸入，然后poj又崩了，半個小時之后終于好了，終于A了，我真的佛了

最后，辣雞poj

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int n,m,limit;struct Edge {int to,next; }edge[N<<1];int head[N],cnt;//鏈式前向星用int val[N];//樹上差分用int deep[N],dp[N][20];//樹上倍增用void addedge(int u,int v) {edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].to=u;edge[cnt].next=head[v];head[v]=cnt++; }void dfs1(int u,int f,int dep)//樹上倍增 {deep[u]=dep;dp[u][0]=f;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(v==f)continue;dfs1(v,u,dep+1);} }int LCA(int a,int b) {if(deep[a]<deep[b])swap(a,b);for(int i=limit;i>=0;i--)if(deep[a]-deep[b]>=(1<<i))a=dp[a][i];if(a==b)return a;for(int i=limit;i>=0;i--)if(dp[a][i]!=dp[b][i]){a=dp[a][i];b=dp[b][i];}return dp[a][0]; }int sum[N];//樹上前綴和void dfs2(int u,int f)//樹上前綴和 {sum[u]=val[u];for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(v==f)continue;dfs2(v,u);sum[u]+=sum[v];} }void init() {memset(head,-1,sizeof(head));memset(val,0,sizeof(val));limit=log2(n)+1; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d",&n,&m)!=EOF){init();for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v);}dfs1(1,0,0);for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);val[u]++;val[v]++;val[LCA(u,v)]-=2;}dfs2(1,0);int ans=0;for(int i=2;i<=n;i++){if(sum[i]==0)ans+=m;else if(sum[i]==1)ans++;}printf("%d\n",ans);}return 0; }

?

總結

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

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