【BZOJ1149】【APIO2007】風鈴（完全二叉樹+dp）

Description

Input

Output

輸出僅包含一個整數。表示最少需要多少次交換能使風鈴滿足Ike的條件。如果不可能滿足，輸出-1。

Sample Input

6

2 3

-1 4

5 6

-1 -1

-1 -1

-1 -1

Sample Output

2

題目大意：給定一棵完全二叉樹，可以交換某個節點的左右兒子，求最少交換多少次數，可以使所有的葉節點深度相差不超過1,且深度較大的葉節點都在深度較小的葉節點左側。

題解：

無解的情況好多……

首先，最大和最小的節點深度超過1就無解了。其次，如果最大深度和最小深度節點分别在一顆子樹的左子樹和右子樹中，也是無解的。

是以，隻要先做一遍DFS預處理出節點深度的有關資料，再dp就好了，注意分類就行了。

代碼如下：

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#define ll long long
#define inf 0x7f7f7f7f
using namespace std; 
int n,l[],r[],ans,minn=inf,maxx; 
void dfs(int u,int dep)
{
    if(u==-)
    {
        maxx=max(maxx,dep);
        minn=min(minn,dep);
        return ;
    }
    dfs(l[u],dep+);dfs(r[u],dep+);
    return ;
}
int work(int u,int dep)
{
    int x=,y=;
    if(u==-)
    {
        if(dep==minn) return ;
        return ;
    }
    x=work(l[u],dep+),y=work(r[u],dep+);
    if((x== && y==) || (x== && y==) || (x== && y==)) ans++;  
    if(x== && y==){puts("-1");exit();}  
    return (x|y); 
}
int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++) scanf("%d%d",&l[i],&r[i]);
    dfs(,);
    if(maxx-minn>) return puts("-1"),;
    if(maxx==minn) return puts("0"),;
    work(,);
    printf("%d\n",ans);
    return ;
}