[JZOJ5969] 世界线修理（欧拉回路）

题目

描述

>

题目大意

给你两棵树，让你对每个点赋权，使得在两棵树中的任意子树的和绝对值为$1$。

---

比赛思路

其实我一开始理解错题意了……

---

正解

首先，我们可以判断每个点权的奇偶性。
如果一个点有偶数个儿子，显然它们的和为偶数，所以这个点权为奇数。
如果一个点有奇数个儿子，显然它们的和为奇数，所以这个点权为偶数。
所以在两棵树中，分别计算它儿子的个数。如果它们的奇偶性不一样，那么一定impossible。

现在有一个问题，如果它们的奇偶性一样，那么是否一定有一种可行的方案呢？
的确是可行的。
然后发现必定有一种可行的方案满足每个点的权值只能为$-1,0,1$
感性理解一下可能就出来了。

咳咳，先不要讨论这么多。
接下来有一个巧妙的东西，叫欧拉回路。
我也不知道出题人的脑洞究竟有多大，这题居然可以和欧拉回路建立起联系！
首先，我们把两个树构出来。其中对于根节点，我们用一个超级源来连接它们。
显然对于每一个度数为偶数的点，因为它们有奇数个儿子，所以它们的权值为$0$。
反之，对于每一个度数为奇数的点，它们的权值为$-1$或$1$。
然后枚举每一个点，如果这个点的度数为奇数，那么就将两个树中对应的点连接起来。（这条边叫横插边）
然后我们就发现这个图中，每个点的度数都是偶数，那么就一定存在一个欧拉回路。
随便从一个点出发，找出一条欧拉回路。
随便以某个树为准，对于每一个横插边，看看它们的方向，如果是进入这棵树，那么这个横插边对应的两点的点权为$-1$，否则为$1$。
当然，反过来也一样。
然后答案就出来了。

能想出这个解法的人一定是个天才……
接下来我们来证明这个解法为什么是正确的。
首先设四类环：
一类环为，从某个点开始，先走儿子边，然后从儿子边回来。
二类环为，从某个点开始，先走儿子边，然后从父亲边回来。
三类环为，从某个点开始，先走横插边，然后从父亲边回来。
四类环为，从某个点开始，先走儿子边，然后从横插边回来。
当然，每个环的走向反过来都是等价的。
然后考虑每个环的代价：
对于一类环，就是在两棵树之间跳来跳去，但代价都是在这个点的子树以内计算的。进来的代价为$-1$，出去的代价为$1$，所以一类环的代价是$0$。
四类环也是同样的道理，代价为$0$.
对于二类环，也是在两棵树之间跳来跳去，但是，由于最后从父亲边回来，意味着最后一次从横插边跳回来的时候计算的代价不在这个点的子树内，所以二类环的代价是$-1$或$1$。
三类环也是同样的道理，代价也是$-1$或$1$。

然后我们再看看每一个点：
如果一个点有奇数个儿子，那么它的度数为偶数，是没有横插边的。所以只有若干个一类环和一个二类环，所以代价为$-1$或$1$。
如果一个点有偶数个儿子，那么它有横插边。所以，要么是若干个一类环和一个三类环，要么是若干个一类环和一个二类环和一个四类环。然后可以发现代价都是$-1$或$1$。
得证……

还有一个问题，为什么要设置一个超级源？
仔细想一下，设置一个超级源之后，根节点就变得跟普通点一样了，它们的性质也一样。
而且你会发现，如果不设超级源，那么仅仅用这个方法并不成立，或许要加点特判什么的……

---

代码

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
int n;
int fa1[N+1],fa2[N+1];
int rd1[N+1],rd2[N+1];
struct EDGE{
	int to;
	EDGE *las;
	bool bz;
} e[N*6+1];
int ne=-1;
EDGE *last[N*2+1];
#define rev(ei) (e+(int((ei)-e)^1))
inline void link(int u,int v){
	e[++ne]={v,last[u],1};
	last[u]=e+ne;
	e[++ne]={u,last[v],1};
	last[v]=e+ne;
}
int w[N*6+1],nw;
void dfs(int);
int ans[N+1];
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;++i){
		scanf("%d",&fa1[i]);
		if (fa1[i]!=-1)
			rd1[fa1[i]]++;
	}
	for (int i=1;i<=n;++i){
		scanf("%d",&fa2[i]);
		if (fa2[i]!=-1)
			rd2[fa2[i]]++;
	}
	for (int i=1;i<=n;++i)
		if ((rd1[i]^rd2[i])&1){//当奇偶性不同时
			printf("IMPOSSIBLE
");
			return 0;
		}
	printf("POSSIBLE
");
	for (int i=1;i<=n;++i){
		//i<<1表示i在第一棵树的点，i<<1|1表示i在第二棵树的点
		link(i<<1,fa1[i]!=-1?fa1[i]<<1:0);
		link(i<<1|1,fa2[i]!=-1?fa2[i]<<1|1:0);
		if (~rd1[i]&1)
			link(i<<1,i<<1|1);
	}
	w[0]=1<<1;
	dfs(1<<1);
	for (int i=1;i<=nw;++i)
		if ((w[i-1]^w[i])==1){//如果两个点互为对应点
			if (w[i]&1)
				ans[w[i]>>1]=-1;
			else
				ans[w[i]>>1]=1;
		}	
	for (int i=1;i<=n;++i)
		printf("%d ",ans[i]);
	return 0;
}
void dfs(int x){//求欧拉回路
	for (EDGE *ei=last[x];ei;ei=last[x]){
		last[x]=ei->las;//将这条边删除
		if (ei->bz){
			rev(ei)->bz=ei->bz=0;
			dfs(ei->to);
		}
	}
	w[++nw]=x;
}

---

总结

说实话，其实感觉上这题没什么好总结的。
因为这题能想出来实在是太变态了。