题解：P11479 [NordicOI 2017] Subway

· · 题解

Solution

首先，声称答案为边集对称差的大小。显然这是答案的下界，我们需要构造一种方案使得它成立。

（这种思想的好处在于，整道题直接变成了一道构造题，可以用一些数据结构手段解决，而不是飘忽不定的最优化题）

显然，每次删掉一个不在最终边集里面的边，将树分为两个联通块。由于最终是联通的，所以一定能找到一条未加入的、连接两个联通块的边。

考虑加速该流程。设最终边集的边将图连成若干个联通块，如下图所示（红色的边表示最终边集中的边）

按照深度考虑每个联通块。显然，一定有一条边，一个端点在这个联通块里，另一个端点在这个联通块外。

由于我们是按照深度考虑联通块的，所以每次选择的联通块所在子树内所有节点都在这个联通块里。我们可以在联通块的根处维护所有未被加入的边。断掉联通块的根和其原树上的父亲的连边，并且选择另一条边合并到树上，这相当于合并两个联通块。使用启发式合并即可做到 O(n \log n)（我写了个 set，是双 \log 的，但是过了）

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,fa[MAXN],dep[MAXN],ff[MAXN];
set<pair<int,int>> g,t;
vector<int> G[MAXN];
int find(int k) {return (fa[k]==k)?k:(fa[k]=find(fa[k]));}
set<pair<int,int>> st[MAXN];
void merge(set<pair<int,int>> &u,set<pair<int,int>>& v) {
    if(u.size()<v.size()) swap(u,v);
    for(auto pr:v) u.insert(pr);
    v.clear();
    return ;
}
void dfs(int u,int f) {
    dep[u]=dep[f]+1,ff[u]=f;
    for(auto v:G[u]) if(v!=f) {
        if(t.find({min(v,u),max(u,v)})!=t.end()) fa[v]=u;
        else fa[v]=v;
        dfs(v,u);
    }
    return ;
}
vector<pair<pair<int,int>,pair<int,int>>> ans;
struct INFO {int dep,u;};
bool operator <(INFO A,INFO B) {return A.dep<B.dep;}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    ffor(i,1,n-1) {
        int u,v;
        cin>>u>>v,u++,v++;
        G[u].push_back(v),G[v].push_back(u),g.insert({min(u,v),max(u,v)});
    }
    ffor(i,1,n-1) {
        int u,v;
        cin>>u>>v,u++,v++,t.insert({min(u,v),max(u,v)});
    }
    fa[1]=1,dfs(1,0);
    for(auto pr:t) {
        int u=pr.first,v=pr.second;
        if(find(u)!=find(v)) st[find(u)].insert({u,v}),st[find(v)].insert({u,v});   
    }
    priority_queue<INFO> q;
    ffor(i,1,n) if(find(i)==i) q.push({dep[i],i});
    while(!q.empty()) {
        int u=q.top().u,x1=-1,x2=-1;
        if(u==1) break ;
        q.pop();
        while(1) {
            auto pr=*st[u].begin();
            st[u].erase(pr);
            x1=pr.first,x2=pr.second;
            if(find(x1)!=find(x2)) break ;
        }
        if(find(x1)!=u) swap(x1,x2);
        ans.push_back({{ff[u]-1,u-1},{x1-1,x2-1}});
        merge(st[find(x2)],st[find(u)]),fa[u]=find(x2);
    }
    cout<<ans.size()<<'\n';
    for(auto pr:ans) cout<<pr.first.first<<' '<<pr.first.second<<' '<<pr.second.first<<' '<<pr.second.second<<'\n';
    return 0;
}