BZOJ 1149 風鈴完整解析

給定完全二叉樹，可交換任意節點左右子樹。求最少交換次數使所有葉子深度差 ≤ 1，且較深葉子全在較淺葉子左側。

核心觀察

1. 先 DFS 求最大/最小葉子深度，差 ≥ 2 ⇒ 無解（-1）
2. 差 = 0 ⇒ 已滿足，答案 0
3. 差 = 1 ⇒ 需調整。對每個節點，其左右子樹只能包含「深葉子」或「淺葉子」其中一種，不能混合

樹形 DP 狀態定義

DFS 返回值編碼子樹葉子類型：

• 1：僅有淺葉子（深度 = min_dpt）
• 2：僅有深葉子（深度 = max_dpt）
• 3：同時有深淺葉子（非法）

轉移邏輯：

int l = dfs(left), r = dfs(right);
if (l == 3 || r == 3) no_solution(); // 子樹非法

// 查表決定是否需交換
// a[l][r] = 0: 不交換合法  1: 需交換  3: 非法
static const int a[4][4] = {
    {0,0,0,0},
    {0,0,0,0},
    {0,1,0,1},
    {0,1,0,0}
};
ans += a[l][r];
return l | r; // 合併類型：1|2=3(非法), 1|1=1, 2|2=2

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100100;

int n, ans = 0;
int max_dpt = 0, min_dpt = INT_MAX;
int ls[MAXN], rs[MAXN];

void dfs_depth(int u, int dpt) {
    if (u == -1) {
        max_dpt = max(max_dpt, dpt);
        min_dpt = min(min_dpt, dpt);
        return;
    }
    dfs_depth(ls[u], dpt + 1);
    dfs_depth(rs[u], dpt + 1);
}

int dfs_dp(int u, int dpt) {
    if (u == -1) return (dpt == min_dpt) ? 2 : 1;
    
    int l = dfs_dp(ls[u], dpt + 1);
    int r = dfs_dp(rs[u], dpt + 1);
    
    if (l == 3 && r == 3) { cout << -1 << endl; exit(0); }
    
    static const int a[4][4] = {
        {0,0,0,0}, {0,0,0,0},
        {0,1,0,1}, {0,1,0,0}
    };
    ans += a[l][r];
    return l | r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> ls[i] >> rs[i];
    
    dfs_depth(1, 1);
    if (max_dpt - min_dpt >= 2) return cout << -1 << endl, 0;
    if (max_dpt == min_dpt) return cout << 0 << endl, 0;
    
    dfs_dp(1, 1);
    cout << ans << endl;
    return 0;
}

關鍵點總結

• 兩次 DFS：第一次統計深度範圍，第二次計算最小交換
• 狀態壓縮：用 1/2/3 編碼葉子類型，位運算合併
• 查表決策：4×4 表格覆蓋所有左右子樹組合
• 完全二叉樹性質：節點編號 1~n，-1 表示空