洛谷 P3621 APIO2007 风铃

url: https://www.luogu.com.cn/problem/P3621

tag:
动态规划，树形DP

思路：
用 tr[u][0/1] 来存二叉树。做两次dfs第一次求出最大的深度和最小的深度，如果相差大于1直接输出-1。第二次dfs从下到上递归，设计返回值为0/1/2分别表示都是浅层，都是深层和混合。当左边为浅层，右边为深层或者左边为混合，右边为深层时交换答案加1，如果存在某个节点两边都是混合的情况时说明无论怎么交换都不会改变当前的情况，则输出-1程序结束。最后如果存在一个方案使得可以交换成功就输出答案ans。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int tr[N][2],ans, mi = 0x3f3f3f3f, mx;
int n;
void dfs1(int u, int dep)
{
    if (u == -1)
    {
        mi = min(mi, dep);
        mx = max(mx, dep);
        return;
    }
    dfs1(tr[u][0], dep + 1), dfs1(tr[u][1], dep + 1);
}
int dfs2(int u, int dep)
{
    if (u == -1) return (dep != mi);
    int x = dfs2(tr[u][0], dep + 1);
    int y = dfs2(tr[u][1], dep + 1);
    ans += (!x && y) || (x == 2 && y == 1);
    if (x == 2 && y == 2)
    {
        cout << -1;
        exit(0);
    }
    if (x + y == 1 || x == 2 || y == 2) return 2;
    if (!(x + y)) return 0;
    return 1;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> tr[i][0] >> tr[i][1];
    dfs1(1, 0);
    if (mx - mi > 1) cout << -1 << endl;
    else if (mi == mx) cout << 0 << endl;
    else
    {
        int _ = dfs2(1, 0);
        cout << ans << endl;
    }
    return 0;
}