题解 [email protected]洛谷 【[APIO2007]风铃】

CSP2020 快到了,感觉自己 dp 太菜了,补了很多 dp >_<


题意(经过 OI 化魔改):给定一棵二叉树,每次可以交换一个节点的左右儿子,使这棵二叉树是完全二叉树。

思路:容易想到如下几种情况。

情况 11 :容易想到,若所有叶子节点中最深的深度和最浅的深度之差大于 11,那么无解,因为此时没有办法通过交换左右儿子将深度差减少。

情况 22 :如果所有叶子深度均相同,直接输出 00

以上情况可以通过一遍 dfs 求深度解决。

情况 33 :对于一个节点,如果左子树全部为深度浅的节点,且右子树存在深度深的节点,此时需要进行一次交换。

情况 44 :对于一个节点,如果左子树存在深度深、浅的两种节点,且右子树全部为深度深的节点,此时需要进行一次交换。

情况 55 :对于一个节点,如果左、右子树均存在深度深、浅的两种情况,那么无解,因为无论怎么交换,总存在左子树的深度浅的节点比右子树的深度深的节点不符合题意。

以上情况在第二遍 dfs 时统计。


实现细节:第一遍 dfs 就是正常的求深度,没什么好说的,主要说说第二遍 dfs。

第二遍 dfs 的返回值设计为 0/1/20/1/2,分别表示当前结点为根的子树全部为深度浅的节点、深度深的节点,或者二者皆有。在递归返回的时候,我们判断左、右子树返回值进行处理即可。


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5, inf = 0x3f3f3f3f; 

int n, son[N][2], mi = inf, ma, ans;
void dfs(int u, int k) {
	if(u == -1) return (mi=min(mi, k)), (ma=max(ma, k)), void();
	dfs(son[u][0], k+1);
	dfs(son[u][1], k+1);
}
int dfs2(int u, int k) {
	if(u == -1) return (k != mi);
	int x = dfs2(son[u][0], k+1);
	int y = dfs2(son[u][1], k+1);
	ans += ((!x && y) || (x == 2 && y == 1));
	if(x == 2 && y == 2) exit((puts("-1"), 0));
	if(x == 2 || y == 2 || x + y == 1) return 2;
	if(!(x + y)) return 0;
	return 1;
}

int main() {
	scanf("%d", &n);
	for(int i=1;i<=n;i++) scanf("%d%d", &son[i][0], &son[i][1]);
	dfs(1, 0);
	if(ma - mi > 1) return puts("-1"), 0;
	if(ma == mi) return puts("0"), 0;
	int _ = dfs2(1, 0);
	printf("%d\n", ans);
	return 0;
}