题目分析

问题重述

我们有一棵深度为 $n$ 的满二叉树，有 $2^n$ 个叶节点，每个叶节点有一个 $1$ 到 $2^n$ 的排列作为符文值。

游戏规则：

• Alice：可以在预算 $K$ 内唤醒一些非叶节点的守卫
• Bob：知道 Alice 的唤醒选择后，在迷宫中行走
• 行走规则：
  • 守卫被唤醒：必须左→右顺序访问
  • 守卫沉睡：可以自由选择左→右或右→左顺序
• 目标：
  • Bob：希望最终序列 $Q$ 字典序最小
  • Alice：希望最终序列 $Q$ 字典序最大

关键观察

1. 二叉树结构：节点 $u$ 的左儿子是 $2u$，右儿子是 $2u+1$
2. 访问顺序的影响：
   • 守卫唤醒：固定访问顺序（左子树先于右子树）
   • 守卫沉睡：可以交换左右子树的访问顺序
3. 字典序博弈：Alice 和 Bob 在字典序上目标相反

解法思路

方法：树形DP + 贪心

核心思想

从根节点开始，逐层决策。对于每个子树，我们计算在不同预算下，Alice 能保证的该子树产生序列的最小字典序（从Bob的角度）。

状态设计

设 $dp[u][c]$ 表示在节点 $u$ 的子树中，使用不超过 $c$ 的魔力值，Alice 能保证的该子树产生序列的最小字典序。

由于字典序难以直接作为状态，我们改为存储在预算 $c$ 下，该子树能产生的最小首元素。

状态转移

对于节点 $u$：

• 情况1：不唤醒 $u$ 的守卫
  • Bob 可以选择先访问左子树或右子树
  • Alice 需要选择预算分配使两个子树的首元素都尽可能大
• 情况2：唤醒 $u$ 的守卫（花费 $w_u$）
  • 访问顺序固定为左→右
  • Alice 的预算减少 $w_u$

算法框架

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

const int MAXN = (1 << 16) + 5;
const ll INF = 1e18;

int n;
ll K;
ll w[MAXN];
int q[MAXN];
vector<int> result;

// 获取节点u的子树中叶节点的符文值
vector<int> get_leaves(int u, int depth) {
    vector<int> leaves;
    if (depth == n) {
        leaves.push_back(q[u]);
    } else {
        auto left_leaves = get_leaves(2 * u, depth + 1);
        auto right_leaves = get_leaves(2 * u + 1, depth + 1);
        leaves.insert(leaves.end(), left_leaves.begin(), left_leaves.end());
        leaves.insert(leaves.end(), right_leaves.begin(), right_leaves.end());
    }
    return leaves;
}

// DP状态：dp[u][c] = 在节点u子树使用预算c能保证的最小首元素
ll dp[MAXN][105];  // 第二维需要根据数据范围调整

void solve_dp(int u, int depth, ll budget) {
    if (depth == n) {
        // 叶节点：首元素就是该叶节点的符文值
        dp[u][0] = q[u];
        for (int c = 1; c <= budget; c++) {
            dp[u][c] = q[u];  // 叶节点没有守卫可唤醒
        }
        return;
    }
    
    int left = 2 * u, right = 2 * u + 1;
    
    // 递归求解子树
    solve_dp(left, depth + 1, budget);
    solve_dp(right, depth + 1, budget);
    
    // 情况1：不唤醒u的守卫
    for (ll c = 0; c <= budget; c++) {
        ll best = INF;
        // Bob可以选择先访问左子树或右子树
        // 分配预算c = c1 + c2
        for (ll c1 = 0; c1 <= c; c1++) {
            ll c2 = c - c1;
            // 方案A：先左后右
            ll option1 = min(dp[left][c1], dp[right][c2]);
            // 方案B：先右后左  
            ll option2 = min(dp[right][c1], dp[left][c2]);
            // Bob选择字典序更小的方案
            best = min(best, max(option1, option2));
        }
        dp[u][c] = best;
    }
    
    // 情况2：唤醒u的守卫
    if (budget >= w[u]) {
        ll cost = w[u];
        for (ll c = cost; c <= budget; c++) {
            ll remaining = c - cost;
            ll best = INF;
            // 固定顺序：先左后右
            for (ll c1 = 0; c1 <= remaining; c1++) {
                ll c2 = remaining - c1;
                ll option = min(dp[left][c1], dp[right][c2]);
                best = min(best, option);
            }
            dp[u][c] = max(dp[u][c], best);  // Alice选择更好的方案
        }
    }
}

// 根据DP结果重建答案
void reconstruct(int u, int depth, ll budget, vector<int>& res) {
    if (depth == n) {
        res.push_back(q[u]);
        return;
    }
    
    int left = 2 * u, right = 2 * u + 1;
    
    // 检查Alice的最优选择
    ll best_val = dp[u][budget];
    
    // 尝试两种情况
    bool awakened = false;
    ll used_budget = 0;
    
    // 情况2：唤醒守卫（如果可能且更优）
    if (budget >= w[u]) {
        ll remaining = budget - w[u];
        for (ll c1 = 0; c1 <= remaining; c1++) {
            ll c2 = remaining - c1;
            if (min(dp[left][c1], dp[right][c2]) == best_val) {
                awakened = true;
                used_budget = w[u];
                // 固定顺序：先左后右
                reconstruct(left, depth + 1, c1, res);
                reconstruct(right, depth + 1, c2, res);
                break;
            }
        }
    }
    
    if (!awakened) {
        // 情况1：不唤醒守卫，Bob选择顺序
        for (ll c1 = 0; c1 <= budget; c1++) {
            ll c2 = budget - c1;
            // Bob会选择字典序更小的顺序
            ll option1 = min(dp[left][c1], dp[right][c2]);  // 先左后右
            ll option2 = min(dp[right][c1], dp[left][c2]);  // 先右后左
            
            if (max(option1, option2) == best_val) {
                if (option1 <= option2) {
                    // Bob选择先左后右
                    reconstruct(left, depth + 1, c1, res);
                    reconstruct(right, depth + 1, c2, res);
                } else {
                    // Bob选择先右后左
                    reconstruct(right, depth + 1, c1, res);
                    reconstruct(left, depth + 1, c2, res);
                }
                break;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    
    while (T--) {
        cin >> n >> K;
        int node_count = (1 << n) - 1;
        for (int i = 1; i <= node_count; i++) {
            cin >> w[i];
        }
        int leaf_start = (1 << n);
        int leaf_end = (1 << (n + 1)) - 1;
        for (int i = leaf_start; i <= leaf_end; i++) {
            cin >> q[i];
        }
        
        // 初始化DP数组
        for (int i = 0; i < MAXN; i++) {
            for (int j = 0; j < 105; j++) {
                dp[i][j] = INF;
            }
        }
        
        // 求解DP
        solve_dp(1, 0, min(K, 100LL));  // 预算上限取min(K, 100)避免状态爆炸
        
        // 重建答案
        vector<int> result;
        reconstruct(1, 0, min(K, 100LL), result);
        
        // 输出结果
        for (int i = 0; i < (1 << n); i++) {
            cout << result[i] << (i == (1 << n) - 1 ? "\n" : " ");
        }
    }
    
    return 0;
}

优化策略

预算压缩

由于 $K$ 可能很大（$10^{12}$），但实际有效预算不会太大，可以进行预算压缩：

// 预算压缩：只考虑有意义的预算值
vector<ll> compress_budget(ll max_budget, const vector<ll>& costs) {
    set<ll> meaningful;
    meaningful.insert(0);
    
    for (ll cost : costs) {
        set<ll> new_set;
        for (ll b : meaningful) {
            if (b + cost <= max_budget) {
                new_set.insert(b + cost);
            }
        }
        meaningful.insert(new_set.begin(), new_set.end());
    }
    
    return vector<ll>(meaningful.begin(), meaningful.end());
}

更高效的状态表示

使用 map<ll, ll> 来存储DP状态，避免维度爆炸：

map<ll, ll> dp[MAXN];  // dp[u][budget] = min_first_element

void solve_dp_optimized(int u, int depth) {
    if (depth == n) {
        dp[u][0] = q[u];
        return;
    }
    
    int left = 2 * u, right = 2 * u + 1;
    solve_dp_optimized(left, depth + 1);
    solve_dp_optimized(right, depth + 1);
    
    // 合并左右子树的状态
    map<ll, ll> new_dp;
    
    // 情况1：不唤醒守卫
    for (auto& [b1, v1] : dp[left]) {
        for (auto& [b2, v2] : dp[right]) {
            ll total_budget = b1 + b2;
            if (total_budget > K) continue;
            
            // Bob的两种选择
            ll option1 = min(v1, v2);  // 先左后右
            ll option2 = min(v2, v1);  // 先右后左
            ll bob_choice = min(option1, option2);
            
            new_dp[total_budget] = max(new_dp[total_budget], bob_choice);
        }
    }
    
    // 情况2：唤醒守卫
    for (auto& [b1, v1] : dp[left]) {
        for (auto& [b2, v2] : dp[right]) {
            ll total_budget = b1 + b2 + w[u];
            if (total_budget > K) continue;
            
            ll alice_choice = min(v1, v2);  // 固定顺序：先左后右
            new_dp[total_budget] = max(new_dp[total_budget], alice_choice);
        }
    }
    
    dp[u] = new_dp;
}

复杂度分析

• 朴素DP：$O(2^n \cdot K^2)$，在 $n \leq 16$ 但 $K$ 很大时不可行
• 优化DP：使用map的状态数是指数级但实际有效状态较少
• 预算压缩：将状态数控制在可接受范围内

算法总结

1. 树形DP：自底向上计算每个子树在不同预算下的最优首元素
2. 博弈分析：考虑Alice和Bob的最优策略
3. 字典序处理：通过保证首元素最优来保证整个序列字典序最优
4. 状态优化：使用map压缩状态，避免维度爆炸

关键技巧

1. 首元素关键：字典序比较中，首元素起决定性作用
2. 预算分配：Alice需要合理分配预算到各个子树
3. 顺序选择：Bob在守卫沉睡时可以自由选择访问顺序
4. 状态合并：高效合并左右子树的状态

这道题综合考察了树形DP、博弈论和字典序优化，是一道很有挑战性的题目。