650E - Clockwork Bomb - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;

const int N=5e5+5;

struct graph{

	struct edge{int v,next;}e[N<<1];

	int head[N],edgenum,fa[N];

	void add(int u,int v){

		e[++edgenum]=edge{v,head[u]};

		head[u]=edgenum;

	}

	void dfs(int u,int f){

		fa[u]=f;

		for(int i=head[u];i;i=e[i].next)

			if(e[i].v^f)dfs(e[i].v,u);

	}

}g1,g2;

int fa[N],cnt,n;

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

struct node{int x,y,u,v;}a[N<<1];

void dfs(int u,int fa){

	for(int i=g1.head[u],v;i;i=g1.e[i].next){

		if((v=g1.e[i].v)==fa)continue;

		dfs(v,u);

		if(find(u)^find(v))a[++cnt]={u,v,find(v),g2.fa[find(v)]};

	}

}

int main(){

	scanf("%d",&n);

	for(int i=1,u,v;i<n;i++){

		scanf("%d%d",&u,&v);

		g1.add(u,v);g1.add(v,u);

	}

	for(int i=1,u,v;i<n;i++){

		scanf("%d%d",&u,&v);

		g2.add(u,v);g2.add(v,u);

	}

	g1.dfs(1,0);g2.dfs(1,0);fa[1]=1;

	for(int i=2;i<=n;i++){

		int f=g2.fa[i];

		if(g1.fa[f]==i||g1.fa[i]==f)fa[i]=f;

		else fa[i]=i;

	}

	dfs(1,0);

	printf("%d\n",cnt);

	for(int i=1;i<=cnt;i++)printf("%d %d %d %d\n",a[i].x,a[i].y,a[i].u,a[i].v);

}