【Codeforces 650E】Clockwork Bomb

  翻了一下列表发现很多人打的是LCT。然而好像并不需要？

  官方题解上说用并查集来做，我就写并查集了。

  首先考虑那些在初态和终态下都出现的边。这些边显然都是不动的，把它们连接的两个点合并起来。合并时要维护这个集合内的点与集合外的点的连边。

  答案很显然为总边数减去不动的边数，即每次删一条原树中的边，并增加一条终态的树上的边。

  按照任意顺序删去原树中要改变的边(u,v)，然后连一条从u所在集合中的点到u所在集合外的点的边，以保证整个图联通。可以保证一定能找到这样的边。（证明？反证，如果没有，那么这个图是不连通的）

  代码里似乎有瑕疵，不过过了CF上的数据我也就不管那么多了。

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=500010;

struct Edge {int x,y;}Ed[maxn];

map <LL,int> M;

int head[maxn],next[maxn<<1],E[maxn<<1],Ecnt;
int Ehead[maxn],Enext[maxn<<1],Etail[maxn<<1],EE[maxn<<1],EEcnt;
int fa[maxn];
int n,m;

void Add_Edge(int x,int y) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;}
void Add_EdgeE(int x,int y,int p) {Enext[++EEcnt]=Ehead[x];if (Ehead[x]==0) Etail[x]=EEcnt;Ehead[x]=EEcnt;EE[EEcnt]=p;Enext[++EEcnt]=Ehead[y];if (Ehead[y]==0) Etail[y]=EEcnt;Ehead[y]=EEcnt;EE[EEcnt]=p;}
int Find(int x) {return fa[x]==x?x:fa[x]=Find(fa[x]);}

void DFS(int x,int father)
{
	for (int i=head[x];i;i=next[i]) if (E[i]!=father) DFS(E[i],x);
	if (x==1) return;
	if (Find(x)==Find(father)) return;
	int now=Ehead[Find(x)];
	while (Ehead[Find(x)] && Find(Ed[EE[now]].x)==Find(Ed[EE[now]].y)) now=Ehead[Find(x)]=Enext[Ehead[Find(x)]];
	if (!now) return;
	int u=Ed[EE[now]].x,v=Ed[EE[now]].y;
	printf("%d %d %d %d\n",father,x,u,v);
	Enext[Etail[Find(u)]]=Ehead[Find(v)];
	Etail[Find(u)]=Etail[Find(v)];
	fa[Find(v)]=Find(u);
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) fa[i]=i;
	for (int i=1,x,y;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		if (x>y) swap(x,y);
		M[(LL)x*n+y]=1;
		Add_Edge(x,y);
	}
	for (int i=1,x,y;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		if (x>y) swap(x,y);
		if (M[(LL)x*n+y]==1) {fa[Find(x)]=Find(y);continue;}
		Ed[++m].x=x,Ed[m].y=y;
	}
	for (int i=1;i<=m;i++) Add_EdgeE(Find(Ed[i].x),Find(Ed[i].y),i);
	printf("%d\n",m);
	DFS(1,0);
	return 0;
}