Codeforces

Luogu

分析

设 $fa_1[u]$ 表示 $u$ 在第一棵树上的父亲,$fa_2[u]$ 表示 $u$ 在第二棵树上的父亲。

现在在第一棵树上 DFS。假设现在在 $u$,如果 $(fa_1[u],u)$ 没有在第二棵树上出现过,那么就把它换成 $(fa_2[u],u)$。

这样子会有一个问题,就是可能 $(fa_2[u],u)$ 已经被连上了。这种情况只要往上跳 $fa_2$ 直到没有连边即可。这个过程用并查集优化一下就好了。

容易发现这样子可以达成目标,而且次数达到了下界。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

int n;
vector<int> G[2][N];

int fa[2][N];
inline void dfs(int k,int u) {
    for (re int v:G[k][u])
        if (v!=fa[k][u]) fa[k][v]=u,dfs(k,v);
}

int f[N];
inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

struct node { int a,b,c,d; };
vector<node> ans;
inline void solve(int u) {
    for (re int v:G[0][u]) {
        if (v==fa[0][u]) continue;
        solve(v);
        if (u!=fa[1][v]&&v!=fa[1][u])
            ans.push_back((node){u,v,find(v),fa[1][find(v)]});
    }
}

int main() {
    n=read();
    for (re int k=0;k<2;++k) {
        for (re int i=1;i<n;++i) { int u=read(),v=read();
            G[k][u].push_back(v); G[k][v].push_back(u);
        }
        dfs(k,1);
    }
    f[1]=1;
    for (re int i=2;i<=n;++i)
        f[i]=(fa[0][i]==fa[1][i]||fa[0][fa[1][i]]==i)?fa[1][i]:i;
    solve(1);
    printf("%lu\n",ans.size());
    for (re node i:ans) printf("%d %d %d %d\n",i.a,i.b,i.c,i.d);
    return 0;
}
最后修改:2019 年 10 月 18 日 04 : 27 PM