题解 P3621 【[APIO2007]风铃】

fy0123 · 2017-10-11 17:15:29 · 题解

感觉楼下代码有点复杂啊（雾

来一个简洁明了的题解= =

首先对于所有玩具如果有深度差超过1的就是无解（显然），所以dfs一遍记录最小最大的深度即可。然后如果有一个点的两颗子树中都含有最小、最大深度，那么这种情况也是无解，因为无论你怎么交换都不能使深度小的全部到右边去。

然后考虑最少交换次数：其实对于每一个节点的左右子树，三种情况需要交换，

1. 左边全是小深度的，右边全是大深度的

2. 左边全是小深度的，右边大小深度都有

3. 左边大小深度都有，右边全是大深度的

dfs搜一遍就好了。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;

const int N = 100010;
int n, ans = 0, Mindep, Maxdep;
bool flag = true;

struct Tree{
    int lc, rc;
}T[N];

inline int read()
{
    char ch = getchar(); int x = 0, flag = 0;
    while (!isdigit(ch)){ if (ch == '-') flag = 1; ch = getchar(); }
    while (isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); }
    return flag ? -x : x;
}

inline void dfs(int u, int s)
{
    if (u == -1){
        Mindep = min(Mindep, s); Maxdep = max(Maxdep, s);
        return;
    }
    dfs(T[u].lc, s+1); dfs(T[u].rc, s+1);
}

inline int solve(int u, int s)
{
    if (u == -1){
        if (s == Mindep) return 0; else return 1;
    }
    int x = solve(T[u].lc, s+1);
    int y = solve(T[u].rc, s+1);
    if ((x == 0 && y == 1) || (x == 2 && y == 1) || (x == 0 && y == 2)) ans ++;
    if (x == 2 || y == 2){
        if (x == 2 && y == 2) flag = false; return 2;
    }
    if (x+y == 1) return 2;
    if (x+y == 0) return 0; else return 1;
}

int main()
{
    n = read();
    for (int i = 1; i <= n; i ++) T[i].lc = read(), T[i].rc = read();
    Mindep = 1e9; Maxdep = 0; dfs(1, 0);
    if (Maxdep-Mindep > 1){ puts("-1"); return 0; }
    if (Maxdep-Mindep == 0){ puts("0"); return 0; }
    solve(1, 0);
    if (!flag){ puts("-1"); return 0; }
    printf("%d\n", ans);
    return 0;
}