題目鏈接

https://atcoder.jp/contests/agc014/tasks/agc014_e

題解

完了考場上樹剖做法都沒想到是不是可以退役了。。。

首先有一個巨難寫的據說是\(O(n\log^3n)\)的樹剖+樹套樹做法:
對于每條紅邊\((u,v)\), 給藍樹上兩點間路徑\(+1\), 然后每次選出一個值為\(1\)的邊，找到覆蓋它的紅邊然后把這條\(1\)的邊斷掉加上紅邊，再去掉紅邊的影響。

下面來說正解。
依然是上面的思路，然后發現假設斷掉前\((i-1)\)條藍邊之后形成的聯通塊的集合是\(B_i\), 連上從第\(i\)條到第\(n\)條的紅邊之后形成的連通塊集合是\(R_i\), 那么答案為YES當且僅當對于任意\(2\le i\le n\), \(R_i=B_i\).
于是可以得到如下轉化: 一開始圖上有\(n\)個點\(2(n-1)\)條邊，若兩條邊重合則把其連接的兩點縮成同一點，問整個圖最后能不能縮成一個點。
啟發式合并即可。維護目前所有重邊的隊列、每個點的相鄰點以及圖上所有的邊。每次從隊列里取出一條邊，然后把度數較小的點的邊全部轉移到度數較大的點上。如果能如此重復做\((n-1)\)次，那么答案是YES, 否則為NO. 相鄰點可以用set維護，圖上邊可以用map維護。
時間復雜度\(O(n\log^2n)\).

代碼

#include<cstdio> #include<cstdlib> #include<iostream> #include<cassert> #include<algorithm> #include<map> #include<set> #include<queue> #include<utility> #define pii pair<int,int> #define mkpr make_pair using namespace std;const int N = 1e5; multiset<int> ae[N+3]; map<pii,int> g; queue<pii> que; int n;void insertedge(int u,int v) {if(u==v) return;if(u>v) swap(u,v);ae[u].insert(v); ae[v].insert(u);g[mkpr(u,v)]++;if(g[mkpr(u,v)]==2) {que.push(mkpr(u,v));} }void deleteedge(int u,int v) {ae[v].erase(ae[v].find(u));if(u>v) swap(u,v);if(g.count(mkpr(u,v))) {g.erase(mkpr(u,v));} }int main() {scanf("%d",&n);for(int i=1; i<=2*(n-1); i++){int u,v; scanf("%d%d",&u,&v);insertedge(u,v);}for(int i=1; i<n; i++){while(1){if(que.empty()) {puts("NO"); return 0;}int u = que.front().first,v = que.front().second; que.pop();if(!g.count(mkpr(u,v))) {continue;}if(ae[u].size()<ae[v].size()) swap(u,v);for(set<int>::iterator i=ae[v].begin(); i!=ae[v].end(); i++){int x = *i;deleteedge(v,x);insertedge(u,x);}break;}}puts("YES");return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的AtCoder AGC014E Blue and Red Tree (启发式合并)的全部內容，希望文章能夠幫你解決所遇到的問題。

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