一、题目
二、解法
根据样例大胆猜结论：所有边都可以被匹配。
证明考虑归纳法，对于 ( t T_1) 的一个叶子 (x)，找到它的父亲 (y)，在第二棵树上找到 ((x,y)) 路径上连接 (x) 的边 ((x,t))，把边 ((x,y)) 和边 ((x,t)) 连接，然后把其他连向 (x) 的边都连向 (y)，显然这和原图等价，那么两棵树的大小都同时缩小 (1)，那么就归纳到了更小的情况，所以归纳到最后一定是完美匹配。
考虑模拟上面的过程，但是断开的边数量太多直接 ( t lct) 过不了。
优化删边的方法其实就是建虚点，这里我们可以把 (x) 当作虚点，((x,y)) 之间连一条假边，在匹配的时候我们需要找到 ((x,y)) 之间第一条真边，时间复杂度 (O(nlog n))
三、总结
树问题：简单角度考虑（根、叶子、中心(...)），归纳法求证。
#include <cstdio>
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;
const int M = 500005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,a[M],x[M],y[M],fa[M],d[M];vector<int> g[M];
namespace lct
{
int fa[M],ch[M][2],sz[M],v[M],fl[M],st[M];
int chk(int x)
{
return ch[fa[x]][1]==x;
}
int nrt(int x)
{
return ch[fa[x]][0]==x || ch[fa[x]][1]==x;
}
void flip(int x)
{
if(!x) return ;
swap(ch[x][0],ch[x][1]);
fl[x]^=1;
}
void down(int x)
{
if(!x) return ;
if(fl[x])
{
flip(ch[x][0]);
flip(ch[x][1]);
fl[x]=0;
}
}
void up(int x)
{
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+v[x];
}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
ch[y][k]=w;fa[w]=y;
if(nrt(y)) ch[z][chk(y)]=x;fa[x]=z;
ch[x][k^1]=y;fa[y]=x;
up(y);up(x);
}
void splay(int x)
{
int z=x,t=0;st[++t]=z;
while(nrt(z)) z=fa[z],st[++t]=z;
while(t) down(st[t--]);
while(nrt(x))
{
int y=fa[x];
if(nrt(y))
{
if(chk(x)==chk(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
}
void access(int x)
{
for(int y=0;x;x=fa[y=x])
splay(x),ch[x][1]=y,up(x);
}
void makert(int x)
{
access(x);splay(x);flip(x);
}
void link(int x,int y)
{
makert(x);fa[x]=y;
}
void cut(int x,int y)
{
makert(x);access(y);splay(x);
ch[x][1]=fa[y]=0;up(x);
}
void split(int x,int y)
{
makert(x);access(y);splay(x);
}
int ask(int x)
{
down(x);
if(sz[ch[x][0]]) return ask(ch[x][0]);
if(v[x]) return x;
return ask(ch[x][1]);
}
}
void dfs(int u)
{
for(auto v:g[u])
if(v^fa[u]) fa[v]=u,dfs(v);
}
signed main()
{
n=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<n;i++)
{
x[i]=read();y[i]=read();
lct::v[i+n]=lct::sz[i+n]=1;
lct::link(i+n,x[i]);
lct::link(i+n,y[i]);
}
dfs(1);
for(int i=1;i<=n;i++) d[fa[i]]++;
for(int i=1;i<=n;i++) if(!d[i]) a[++m]=i;
printf("%d
",n-1);
for(int i=1;i<n;i++)
{
int t=a[i];d[fa[t]]--;
if(!d[fa[t]]) a[++m]=fa[t];
lct::split(t,fa[t]);
int id=lct::ask(t);//the first real edge
lct::cut(id,x[id-n]);
lct::cut(id,y[id-n]);
lct::v[id]=lct::sz[id]=0;//clear
lct::link(id,t);
lct::link(id,fa[t]);
printf("%d %d %d %d
",t,fa[t],x[id-n],y[id-n]);
}
}