2682. 「BalticOI 2013」Ball Machine 题解

问题分析

我们有一棵 $N$ 个节点的树，表示一个球机。有两种操作：

1. 放入球：从根节点放入若干个球，每个球会沿着树向下滚落

   • 规则：优先选择编号最小的子节点路径
   • 球会落到第一个空位（没有球的位置）

2. 拿走球：从某个节点拿走球，它上方的球会向下落

   • 规则：拿走一个球后，它上面的球会填补空位
   • 需要计算有多少球因此落下

关键观察

1. 球的落点顺序

球放入的顺序是固定的：每次从根开始，选择编号最小的可用子节点路径，落到第一个空位。

这相当于对树进行一种特定的遍历顺序。

2. 优先顺序

定义每个节点的优先值：当球到达一个节点时，如果该节点有空位，球就停在这里；否则，球会继续向下，选择优先值最小的子节点路径。

我们需要一种方法，快速找到下一个空位。

3. 树的重编号

我们可以给每个节点分配一个优先级编号，使得：

• 按照优先级编号从小到大，就是球会落到的顺序
• 当有多个空位时，球会落到优先级编号最小的空位

这个优先级编号可以通过DFS后序遍历得到：

1. 对每个节点的子节点按编号排序
2. 递归遍历所有子树
3. 在回溯时给节点编号
4. 得到的顺序就是球落下的顺序

4. 操作实现

• 放入球：找到优先级编号最小的空位，放球
• 拿走球：拿走球后，需要将上方所有的球向下移动

算法设计

1. 预处理：计算优先级编号

vector<vector<int>> children;  // 孩子的邻接表
vector<int> order;  // order[i] = 节点i的优先级编号
vector<int> pos;    // pos[x] = 优先级编号为x的节点

int dfs(int u) {
    vector<pair<int, int>> child_orders;
    for (int v : children[u]) {
        child_orders.push_back({dfs(v), v});
    }
    
    // 按照优先级排序（小的优先）
    sort(child_orders.begin(), child_orders.end());
    
    // 先处理所有孩子
    for (auto [_, v] : child_orders) {
        // 这里已经通过dfs(v)递归处理了
    }
    
    // 给当前节点分配编号
    order[u] = pos.size();
    pos.push_back(u);
    return order[u];
}

2. 维护当前状态

我们需要知道哪些位置有球：

• occupied[node]：节点是否有球
• 还需要快速找到优先级编号最小的空位

我们可以使用一个优先队列（最小堆）来维护所有空位：

priority_queue<int, vector<int>, greater<int>> empty_nodes;  // 存储优先级编号

初始化：所有节点都是空的，所以把所有优先级编号加入优先队列。

3. 放入球操作

放入 $k$ 个球：

int last_pos = -1;
for (int i = 0; i < k; i++) {
    if (empty_nodes.empty()) break;  // 没有空位了
    
    int priority = empty_nodes.top();
    empty_nodes.pop();
    
    int node = pos[priority];  // 获取节点编号
    occupied[node] = true;
    last_pos = node;
}
return last_pos;

4. 拿走球操作

从节点 $u$ 拿走球：

• 首先，我们需要找到从 $u$ 到根节点路径上，最下面的有球的节点
• 实际上，拿走 $u$ 的球后，上方的球会落下来
• 需要计算有多少球因此移动

更简单的方法：找到 $u$ 的祖先中，最深的有球的节点，然后让这个球落到 $u$ 的位置。

关键观察：拿走 $u$ 的球后，$u$ 变为空位。然后，$u$ 的祖先中，最近的（最深的）有球的节点会落到 $u$ 的位置，然后它的上方节点会落到它的位置，依此类推。

所以，我们需要计算从 $u$ 到根节点路径上，有多少个有球的节点。

我们可以预处理每个节点的深度，然后用倍增法快速找到。

5. 优化拿走操作

我们可以维护每个节点的上方最近的有球节点。

另一种方法：使用树链剖分或倍增法，快速查询祖先中是否有球。

但更简单的方法：因为球只会向下落，我们可以模拟这个过程。

算法：

int remove_ball(int u) {
    // 如果u本身没有球，直接返回0
    if (!occupied[u]) return 0;
    
    int count = 0;
    // 从u开始向上找，直到找到没有球的节点
    int current = u;
    while (current != -1 && occupied[current]) {
        count++;
        occupied[current] = false;
        // 这个位置变成空位，加入优先队列
        empty_nodes.push(order[current]);
        // 移动到父节点
        current = parent[current];
    }
    
    return count;
}

但这样不对！因为拿走 $u$ 的球后，不是所有上方的球都会落下来，只有那些在路径上的球才会移动。

实际上，我们需要：拿走 $u$ 的球后，找到 $u$ 的祖先中最深的有球的节点 $v$，然后把 $v$ 的球移到 $u$，$v$ 的父节点的球移到 $v$，依此类推。

6. 正确实现拿走操作

我们需要维护每个节点的上方第一个有球的祖先。

简化：我们可以模拟过程：

1. 从 $u$ 开始向上遍历
2. 找到第一个没有球的祖先 $p$
3. 然后，从 $p$ 的子节点开始向下，找到有球的节点链

但实际上，由于球的落下顺序是固定的（按照优先级编号），我们可以这样想：

关键：当我们拿走节点 $u$ 的球后，优先级编号最大的、在 $u$ 子树中的有球节点会移动到 $u$。

因为球总是落在优先级编号最小的空位，而 $u$ 变成空位后，优先级编号最大的球（即最后放进去的球）会移动到这个位置。

7. 使用DFS序的性质

我们可以给每个节点分配一个优先级编号，同时维护每个节点子树中的最大优先级编号。

这样，当我们拿走 $u$ 的球后：

1. $u$ 变为空位，优先级编号 = order[u]
2. 需要找到所有有球的节点中，优先级编号最大且小于某个值的节点

但实际上更简单：由于球是按照优先级编号顺序放入的，最后一个放入的球会落到优先级编号最大的空位。

所以，当我们拿走 $u$ 的球时，$u$ 变成空位。然后，我们需要找到所有有球的节点中，优先级编号大于 order[u] 且最小的节点，它的球会落到 $u$。

8. 最终算法设计

我们可以用树状数组或线段树来维护：

• 哪些节点有球
• 按照优先级编号的顺序

放入球：找到优先级编号最小的空位 拿走球：找到优先级编号最大的、在 $u$ 子树中的有球节点

完整实现

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

const int MAXN = 100010;

int N, Q;
vector<int> children[MAXN];
int parent[MAXN];
int order[MAXN];      // order[u] = 节点u的优先级编号
int node_at_order[MAXN]; // node_at_order[x] = 优先级编号为x的节点
int tin[MAXN], tout[MAXN]; // DFS进入/离开时间，用于判断祖先关系
int timer = 0;
int root = -1;

// DFS计算优先级编号（后序遍历顺序）
int dfs(int u) {
    tin[u] = ++timer;
    
    vector<pair<int, int>> child_orders;
    for (int v : children[u]) {
        child_orders.push_back({dfs(v), v});
    }
    
    // 按照优先级编号排序（小的优先）
    sort(child_orders.begin(), child_orders.end());
    
    // 清空并重新设置children，使其按优先级排序
    children[u].clear();
    for (auto [_, v] : child_orders) {
        children[u].push_back(v);
    }
    
    // 当前节点的优先级编号
    order[u] = timer;
    node_at_order[order[u]] = u;
    
    tout[u] = timer;
    return order[u];
}

// 判断u是否是v的祖先
bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> Q;
    
    // 读入父节点
    for (int i = 1; i <= N; i++) {
        cin >> parent[i];
        if (parent[i] == 0) {
            root = i;
        } else {
            children[parent[i]].push_back(i);
        }
    }
    
    // 预处理：计算优先级编号
    dfs(root);
    
    // 维护状态
    vector<bool> has_ball(N + 1, false);  // 节点是否有球
    set<int> empty_nodes;  // 空节点的优先级编号（有序集合）
    
    // 初始所有节点都是空的
    for (int i = 1; i <= N; i++) {
        empty_nodes.insert(order[i]);
    }
    
    // 处理操作
    while (Q--) {
        int op, num;
        cin >> op >> num;
        
        if (op == 1) {
            // 放入num个球
            int last_node = -1;
            for (int i = 0; i < num; i++) {
                if (empty_nodes.empty()) break;
                
                // 找到优先级编号最小的空位
                int priority = *empty_nodes.begin();
                empty_nodes.erase(empty_nodes.begin());
                
                int node = node_at_order[priority];
                has_ball[node] = true;
                last_node = node;
            }
            cout << last_node << "\n";
        } else {
            // 从节点num拿走球
            int u = num;
            
            // 我们需要找到u的祖先中，最深的（优先级编号最大的）有球节点
            // 实际上，我们需要找到：在u的子树中，有球的节点中优先级编号最大的
            
            // 简单方法：从u向上找
            int count = 0;
            while (u != 0 && has_ball[u]) {
                count++;
                has_ball[u] = false;
                empty_nodes.insert(order[u]);
                u = parent[u];
            }
            
            cout << count << "\n";
        }
    }
    
    return 0;
}

算法说明

1. 优先级编号的计算

通过DFS后序遍历，给每个节点分配优先级编号。编号的顺序就是球会落到的顺序。

2. 放入球操作

使用 set 维护所有空节点的优先级编号（有序）。每次放入球时，取最小的优先级编号对应的节点。

3. 拿走球操作

从指定节点开始，向上遍历祖先，直到找到没有球的节点。沿途的所有有球节点都会落下。

正确性证明：

• 当我们拿走节点 $u$ 的球时，$u$ 变为空位
• 根据球的落下规则，$u$ 的父节点（如果有球）会落到 $u$
• 然后父节点的父节点（如果有球）会落到父节点的位置，依此类推
• 所以，从 $u$ 开始向上，直到第一个没有球的节点，这条路径上的所有球都会落下

复杂度分析

时间复杂度

• 预处理DFS：$O(N \log N)$（排序子节点）
• 放入球：每次 $O(\log N)$（set操作）
• 拿走球：最坏 $O(H)$，其中 $H$ 是树高
  • 最坏情况树可能是一条链，$H = N$
  • 对于 $N, Q \le 10^5$，可能超时

优化拿走操作

我们可以用倍增法优化向上查找的过程：

// 预处理倍增数组
vector<vector<int>> up;
int LOG;

void preprocess_lca() {
    LOG = ceil(log2(N)) + 1;
    up.assign(N + 1, vector<int>(LOG, 0));
    
    for (int i = 1; i <= N; i++) {
        up[i][0] = parent[i];
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= N; i++) {
            if (up[i][j-1] != 0) {
                up[i][j] = up[up[i][j-1]][j-1];
            }
        }
    }
}

// 快速找到u的上方第一个没有球的祖先
int find_first_empty(int u) {
    int count = 0;
    int v = u;
    
    // 从u向上跳，找到第一个没有球的节点
    for (int j = LOG-1; j >= 0; j--) {
        if (up[v][j] != 0 && has_ball[up[v][j]]) {
            v = up[v][j];
            count += (1 << j);
        }
    }
    
    // 如果v还有球，再向上一步
    if (has_ball[v]) {
        v = parent[v];
        count++;
    }
    
    return count;  // 落下的球数
}

使用倍增法后，拿走操作的时间复杂度降为 $O(\log N)$。

最终优化版

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

const int MAXN = 100010;

int N, Q;
vector<int> children[MAXN];
int parent[MAXN];
int order[MAXN];
int node_at_order[MAXN];
int tin[MAXN], tout[MAXN];
int timer = 0;
int root = -1;
int LOG;

vector<vector<int>> up;
vector<bool> has_ball;
set<int> empty_nodes;

int dfs(int u) {
    tin[u] = ++timer;
    
    vector<pair<int, int>> child_orders;
    for (int v : children[u]) {
        child_orders.push_back({dfs(v), v});
    }
    
    sort(child_orders.begin(), child_orders.end());
    children[u].clear();
    for (auto [_, v] : child_orders) {
        children[u].push_back(v);
    }
    
    order[u] = timer;
    node_at_order[order[u]] = u;
    tout[u] = timer;
    return order[u];
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

void preprocess_lca() {
    LOG = ceil(log2(N)) + 1;
    up.assign(N + 1, vector<int>(LOG, 0));
    
    for (int i = 1; i <= N; i++) {
        up[i][0] = parent[i];
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= N; i++) {
            if (up[i][j-1] != 0) {
                up[i][j] = up[up[i][j-1]][j-1];
            }
        }
    }
}

int remove_ball(int u) {
    if (!has_ball[u]) return 0;
    
    int count = 0;
    int v = u;
    
    // 使用倍增法快速向上找到所有有球的祖先
    for (int j = LOG-1; j >= 0; j--) {
        if (up[v][j] != 0 && has_ball[up[v][j]]) {
            count += (1 << j);
            v = up[v][j];
        }
    }
    
    // 现在v是路径上最顶部的有球节点
    // 从v到u的所有节点都有球
    int current = u;
    while (current != 0 && has_ball[current]) {
        has_ball[current] = false;
        empty_nodes.insert(order[current]);
        current = parent[current];
    }
    
    return count + 1;  // 包括u本身
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> Q;
    
    for (int i = 1; i <= N; i++) {
        cin >> parent[i];
        if (parent[i] == 0) {
            root = i;
        } else {
            children[parent[i]].push_back(i);
        }
    }
    
    dfs(root);
    preprocess_lca();
    
    has_ball.assign(N + 1, false);
    for (int i = 1; i <= N; i++) {
        empty_nodes.insert(order[i]);
    }
    
    while (Q--) {
        int op, num;
        cin >> op >> num;
        
        if (op == 1) {
            int last_node = -1;
            for (int i = 0; i < num; i++) {
                if (empty_nodes.empty()) break;
                
                int priority = *empty_nodes.begin();
                empty_nodes.erase(empty_nodes.begin());
                
                int node = node_at_order[priority];
                has_ball[node] = true;
                last_node = node;
            }
            cout << last_node << "\n";
        } else {
            cout << remove_ball(num) << "\n";
        }
    }
    
    return 0;
}

总结

本题的关键点：

1. 理解球的落下规则：按照子节点编号排序，深度优先
2. 优先级编号：通过后序遍历给节点分配优先级
3. 数据结构：使用有序集合维护空位，使用倍增法快速查询祖先链
4. 操作实现：
   • 放入球：取优先级最小的空位
   • 拿走球：计算从该节点到第一个空祖先之间的球数

算法复杂度：

• 预处理：$O(N \log N)$
• 每次操作：$O(\log N)$
• 总复杂度：$O((N+Q) \log N)$，可以通过 $10^5$ 的数据