题意

给你两颗树
每一个操作可以在第一棵树删除一条边，再加上一条边
但是要保证还是一颗树
问你最少步数，和方案

题解

显然地，如果连好的边或者一样的边，我们可以把他缩成一个联通块
一开始SB了。。
纠结在一个很傻逼的问题
就是我们对于第一棵树，我们删除一个点和他父亲的边的时候
再加回去的边是不是随便的
感觉不是啊。。
因为我不知道为什么想到了这种情况

显然不会有啊。。。。。。

然后仔细想一想就知道，随便选择一条边连回去就可以了。。
肯定是连通的。。

于是就好办了
我们只需要维护每一个联通块的边就可以了

怎么合并呢？
启发式合并就可以了。。

步数达到理论下届，肯定是最优的

CODE:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
typedef pair<int,int> PI;
const int N=500005;
struct qq{
   int x,y,last;}e[N*2];int num,last[N];
int n;
void init (int x,int y)
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
set<PI> s[N];
set<PI>::iterator it;
int f[N];
int find (int x){
   return f[x]==x?f[x]:f[x]=find(f[x]);}
void Merge (int x,int y)//两个东西合并 
{x=find(x);y=find(y);if (s[x].size()<s[y].size()) swap(x,y);f[y]=x;for (it=s[y].begin();it!=s[y].end();it++)   s[x].insert(*it);s[y].clear();
}
struct qt
{int x1,y1;int x2,y2;
}Ans[N];int tot=0;
void dfs (int x,int fa)
{for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (y==fa) continue;dfs(y,x);}if (fa==0) return ;int p=x,q=fa;if (p>q) swap(p,q);if (s[find(x)].count(make_pair(p,q))!=0)//一开始就又这条边 {s[find(x)].erase(make_pair(p,q));s[find(fa)].erase(make_pair(p,q));Merge(p,q);}else//更改树边 {p=find(x);PI xx=*s[p].begin();//随便选一条存在的边q=find(xx.first)==p?find(xx.second):find(xx.first);Ans[++tot]=qt{x,fa,xx.first,xx.second};s[p].erase(xx);s[q].erase(xx);Merge(p,q);}
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d",&n);for (int u=1;u<n;u++){int x,y;scanf("%d%d",&x,&y);init(x,y);init(y,x);}for (int u=1;u<=n;u++) f[u]=u;for (int u=1;u<n;u++){int x,y;scanf("%d%d",&x,&y);if (x>y) swap(x,y);s[x].insert(make_pair(x,y));s[y].insert(make_pair(x,y));}dfs(1,0);printf("%d\n",tot);for (int u=1;u<=tot;u++)    printf("%d %d %d %d\n",Ans[u].x1,Ans[u].y1,Ans[u].x2,Ans[u].y2);return 0;
}