Codeforces Round #345 (Div. 1) E Clockwork Bomb

非常好的一道题

首先很容易想到当你拆一条边后加边的次序是随意的

然后我们可以这么想：如果在两个图中都存在的边没有任何意义，所以我们可以在结果图中先把相同边留下，把其他边删去，怎么弄呢，如果是一棵树就好办了，所以剩下就是把一堆树连起来。然后考虑开始的图，对于在结束图中不存在的边我们把它也删了，然后就是从当前节点出发有联通快，这些联通块在第二张图里面也存在，所以下面很简单了，我们只要把当前联通块的祖先与它在结果图中的父亲练一下就好了，那么饿会不会重复呢？不可能，因为在原图中它是一棵树，所以对于一个点不可能有两个父亲，而每次连边的时候只从儿子开始找

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#define mp(a,b) make_pair(a,b)
#define xx first
#define yy second
using namespace std;
const int maxn=500005;
vector<int>g[2][maxn];
int fa[2][maxn];
int pp[maxn];
typedef pair<int,int>p1;
typedef pair<p1,p1>p2;
vector<p2> gg;
int find(int p){
    if(pp[p]==-1||pp[p]==p) return pp[p]=p;
    return pp[p]=find(pp[p]);
}
int panduan(int u,int x,int y){
    if(fa[u][x]==y||fa[u][y]==x) return 1;
    return 0;
}
void dfs(int u,int p,int pa){
    fa[u][p]=pa;
    for(int v:g[u][p]){
        if(v==pa) continue;
        dfs(u,v,p);
    }
}
void solve(int u,int pa){
    for(int v:g[0][u]){
        if(v!=pa){
            solve(v,u);
            if(!panduan(1,u,v)){
                int w=find(v);
                gg.push_back(mp(mp(u,v),mp(w,fa[1][w])));
            }
        }
    }
}
int main()
{
    int i,n;
    cin>>n;
    for(i=0;i<n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[0][x].push_back(y);
        g[0][y].push_back(x);
    }
    for(i=0;i<n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[1][x].push_back(y);
        g[1][y].push_back(x);
    }
    dfs(0,1,-1);
    dfs(1,1,-1);
    memset(pp,-1,sizeof(pp));
    for(i=2;i<=n;i++){
        if(panduan(0,i,fa[1][i])){
            pp[i]=fa[1][i];
        }
    }
    solve(1,-1);
    int p=gg.size();
    printf("%d\n",p);
    for(i=0;i<p;i++){
        printf("%d %d %d %d\n",gg[i].xx.xx,gg[i].xx.yy,gg[i].yy.xx,gg[i].yy.yy);
    }
}