树上博弈 - 题解

标签与难度

标签: 博弈论, 树的直径, 最近公共祖先(LCA), 动态加点, 树上数据结构 难度: 2500

题目大意喵~

各位算法大师们，下午好喵~ 今天我们来玩一个在树上的小游戏，规则是这样哒：

在一棵可爱的树上，有一个小石子，初始放在节点 p 上。还有一个变量 x，初始值为给定的 k。

两个小可爱轮流操作石子：

1. 当前玩家需要找到一个新节点 z，使得它到石子当前位置 p 的距离 dis(p, z) 严格大于 x。
2. 如果找不到这样的 z，当前玩家就输掉游戏啦，呜~
3. 如果能找到，玩家就选择一个满足条件的 z，然后把石子移动到 z，并把 x 的值更新为这次的移动距离，也就是 dis(p, z)。

游戏有两种操作：

• 操作1: 在树上增加一个新节点，并连接到一个已有的节点上。
• 操作2: 给定一个初始状态 (p, k)，判断先手是否必胜。

假设两个玩家都绝顶聪明，总会选择最优的策略。我们要做的就是，对于每个查询，告诉先手能不能赢下这场智慧的较量，喵！

解题思路分析

这真是一道有趣的博弈题呢，喵~ 看到“轮流操作”、“最优策略”，我们的第一反应通常是博弈论，比如SG函数什么的。但是这个游戏的状态 (p, x) 中，x 的取值范围太大了，直接分析状态可不太行呢。

我们来换个角度思考。游戏的核心是，每一轮的移动距离都必须比上一轮更大。谁要是找不到一个更远的节点，谁就输了。

关键的转变：从“怎么走”到“能不能赢”

一个玩家在状态 (p, k) 时，他会怎么想呢？他当然是想移动到一个新位置 z，让对手接下来面对一个“必败”的局面。

那什么样是“必败”的局面呢？假如轮到对手在节点 z 操作，此时的 x 值是 dis(p, z)。如果对手找不到任何一个节点 z' 使得 dis(z, z') > dis(p, z)，那他不就输了吗？

一个节点 u 到树上其他节点的最远距离，我们记为 F(u)。这个 F(u) 其实就是 u 到树的某条直径的两个端点之一的距离。所以，对手在 (z, dis(p, z)) 这个状态下输掉的条件就是 F(z) <= dis(p, z)。

所以，先手在 (p, k) 时，如果能找到一个节点 z，同时满足下面两个条件，他不就直接赢了吗？

1. dis(p, z) > k （这是一个合法的移动）
2. F(z) <= dis(p, z) （移动到 z 之后，对手直接输掉）

如果游戏总是这么简单就好了！但万一先手找不到这样一步就能制胜的 z 呢？他随便走一步，对手是不是就能用同样的方式反过来将他一军？

这就引导我们去思考一个更深层次的问题：一个状态 (p, k) 究竟是不是必胜态？

神奇的“游戏值”

经过一番艰苦的探索（在小鱼干的帮助下！），本喵发现了一个关于这个游戏的惊人结论！对于树上的每一个节点 u，都存在一个只与它自身位置有关的“游戏值”，我们叫它 P(u)。

一个状态 (u, k) 是必败态，当且仅当 P(u) <= k。

这个结论是不是超级强大？它把复杂的博弈过程，简化成了一个简单的数值比较！

那么，这个神奇的 P(u) 到底是什么呢？它和树的直径以及中心有关！

1. 首先，我们找到当前树的一条直径，设它的两个端点是 A 和 B。
2. 然后，我们找到这条直径路径的中心。
   • 如果直径的长度（边数）是偶数，那么中心是唯一的，我们叫它 C。
   • 如果直径的长度是奇数，那么中心是中间那条边上的两个节点，我们叫它们 C1 和 C2。
3. 节点 u 的游戏值 P(u) 就定义为：
   • （单中心情况）P(u) = 2 * dis(u, C)
   • （双中心情况）P(u) = dis(u, C1) + dis(u, C2) （这里的 dis 指的是边的数量哦）

有了这个结论，问题就迎刃而解啦！

对于一个查询 (p, k)，先手是必胜还是必败？

• 如果 P(p) <= k，说明初始状态 (p, k) 就是一个必败态，所以先手必败。
• 如果 P(p) > k，说明初始状态 (p, k) 是一个必胜态。先手可以找到一个节点 z，移动过去，使得 dis(p, z) > k 并且 P(z) <= dis(p, z)（让对手进入必败态）。事实上，可以证明，当 P(p) > k 时，这样的 z 总是存在的！所以先手必胜。

因此，我们的任务就变成了：

1. 动态维护树的直径：每次加入一个新节点，都要检查它是否会形成一条新的、更长的直径。
2. 快速计算距离和中心：这需要我们能够高效地求 LCA (最近公共祖先) 和树上两点距离。

算法步骤

1. 预处理：对初始的 n 个节点的树，我们先用两次 DFS 找到一条直径的端点 A 和 B。然后做一次 O(N log N) 的预处理，为之后用二进制倍增法求 LCA 和距离做准备。
2. 处理加点操作 (1, u)：
   • 一个新的节点 v 连接到 u 上。
   • 我们更新 v 的深度和它的倍增祖先信息。
   • 然后，检查新节点 v 能否更新直径。我们计算 dis(v, A) 和 dis(v, B)。如果 dis(v, A) 大于当前直径长度，那么新的直径就是 (v, A)。如果 dis(v, B) 大于当前直径长度，新的直径就是 (v, B)。更新直径端点 A, B。
3. 处理查询操作 (2, k, p)：
   • 首先，根据当前的直径端点 A, B，找到直径的中心 C (或 C1, C2)。这可以通过从 A 或 B 往上跳 D/2 或 (D-1)/2 步来实现，其中 D 是直径长度。
   • 然后，计算游戏值 P(p)。
   • 最后，比较 P(p) 和 k 的大小，P(p) > k 则先手必胜，否则必败。

这样一来，我们就能优雅地解决这道题了，喵~

代码实现

这是本喵根据上面的思路，精心重构的一份代码，希望能帮助你理解呐！

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAXN = 600010; // 初始N + 查询Q
const int LOGN = 20;

vector<int> adj[MAXN];
int parent[MAXN][LOGN];
int depth[MAXN];
int node_count;

// LCA和距离计算
void dfs_lca(int u, int p, int d) {
    depth[u] = d;
    parent[u][0] = p;
    for (int i = 1; i < LOGN; ++i) {
        if (parent[u][i-1] != 0) {
            parent[u][i] = parent[parent[u][i-1]][i-1];
        } else {
            parent[u][i] = 0;
        }
    }
    for (int v : adj[u]) {
        if (v != p) {
            dfs_lca(v, u, d + 1);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOGN - 1; i >= 0; --i) {
        if (parent[u][i] != 0 && depth[parent[u][i]] >= depth[v]) {
            u = parent[u][i];
        }
    }
    if (u == v) return u;
    for (int i = LOGN - 1; i >= 0; --i) {
        if (parent[u][i] != 0 && parent[v][i] != 0 && parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return parent[u][0];
}

int get_dist(int u, int v) {
    if (u == 0 || v == 0) return -1; // 节点0不存在
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

// 向上跳k步
int jump(int u, int k) {
    for (int i = 0; i < LOGN; ++i) {
        if ((k >> i) & 1) {
            u = parent[u][i];
        }
    }
    return u;
}

// 直径端点
int diameter_a, diameter_b;

// 添加新节点
void add_node(int u, int p) {
    depth[u] = depth[p] + 1;
    parent[u][0] = p;
    for (int i = 1; i < LOGN; ++i) {
        if (parent[u][i-1] != 0) {
            parent[u][i] = parent[parent[u][i-1]][i-1];
        } else {
            parent[u][i] = 0;
        }
    }

    int dist_a = get_dist(u, diameter_a);
    int dist_b = get_dist(u, diameter_b);
    int current_diameter = get_dist(diameter_a, diameter_b);

    if (dist_a > current_diameter) {
        diameter_b = u;
    } else if (dist_b > current_diameter) {
        diameter_a = u;
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    node_count = n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 预处理LCA
    dfs_lca(1, 0, 0);

    // 寻找初始直径
    int farthest_node = 1;
    int max_dist = 0;
    for (int i = 1; i <= n; ++i) {
        int d = get_dist(1, i);
        if (d > max_dist) {
            max_dist = d;
            farthest_node = i;
        }
    }
    diameter_a = farthest_node;
    max_dist = 0;
    for (int i = 1; i <= n; ++i) {
        int d = get_dist(diameter_a, i);
        if (d > max_dist) {
            max_dist = d;
            farthest_node = i;
        }
    }
    diameter_b = farthest_node;

    // 处理查询
    for (int i = 0; i < q; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int p;
            cin >> p;
            node_count++;
            add_node(node_count, p);
        } else {
            int k, p_start;
            cin >> k >> p_start;

            int d_ab = get_dist(diameter_a, diameter_b);
            int center1, center2;

            if (d_ab % 2 == 0) { // 偶数边，奇数点，一个中心
                int half = d_ab / 2;
                center1 = (depth[diameter_a] > depth[diameter_b]) ? jump(diameter_a, half) : jump(diameter_b, half);
                center2 = center1;
            } else { // 奇数边，偶数点，两个中心
                int half = d_ab / 2;
                center1 = (depth[diameter_a] > depth[diameter_b]) ? jump(diameter_a, half) : jump(diameter_b, half);
                center2 = parent[center1][0];
            }

            int game_value = get_dist(p_start, center1) + get_dist(p_start, center2);
            if (game_value > k) {
                cout << "1\n";
            } else {
                cout << "0\n";
            }
        }
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O((N+Q) \log(N+Q))$

  • 预处理: 第一次建立LCA的倍增表需要 $O(N \log N)$。找初始直径需要 $O(N \log N)$（因为每个get_dist是 $O(\log N)$）。
  • 加点操作: 每次加点，更新一个节点的倍增表是 $O(\log(\text{当前节点数}))$，更新直径需要两次距离计算，也是 $O(\log(\text{当前节点数}))$。
  • 查询操作: 每次查询，找到直径中心需要一次 jump 操作和一次 get_dist，都是 $O(\log(\text{当前节点数}))$。计算游戏值需要两次 get_dist，也是 $O(\log(\text{当前节点数}))$。
  • 总共 $Q$ 次操作，总复杂度为 $O((N+Q)\log(N+Q))$。

• 空间复杂度: $O((N+Q) \log(N+Q))$

  • 主要空间开销来自于LCA的倍增表 parent[MAXN][LOGN]。

知识点总结

这道题是多种算法的巧妙结合，做完之后是不是感觉收获满满，喵~

1. 博弈论转化: 核心思想是将一个看似复杂的动态博弈过程，通过一个神奇的“游戏值”P(u)，转化为一个简单的数值判断问题。这是解题的关键，也是最难想到的地方。
2. 树的直径: “游戏值”P(u)的定义依赖于树的直径和中心。因此，我们需要熟练掌握如何寻找和维护树的直径。
3. 动态加点: 题目要求支持在线加点，这意味着我们的数据结构和算法必须能适应树的动态变化。幸运的是，只加叶子节点对LCA和直径维护来说相对友好。
4. LCA与树上距离: 无论是维护直径还是计算游戏值，都离不开高效的树上距离查询。二进制倍增法求LCA是一个非常标准且强大的工具。

总之，这是一道考验综合能力的好题，它告诉我们，有时候看似复杂的博弈问题，背后可能隐藏着优美的数学结构哦！继续加油，探索更多算法的奥秘吧，喵~