题解 P3621 【[APIO2007]风铃】

rui_er · 2020-10-02 21:08:27 · 题解

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

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

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

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

情况 2 ：如果所有叶子深度均相同，直接输出 0。

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

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

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

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

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

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

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

代码：

//By: Luogu@rui_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;
}