「PA 2020」Ogromne drzewo 题解

算法思路

本题使用分块优化和组合博弈论来解决大规模树上的最优策略问题。核心思想是通过预处理和分块技术高效处理多次查询。

关键观察

1. 树结构特性

• 树是分层的，第 $i$ 层每个节点有 $a_i$ 个子节点
• 总节点数可能非常大（达到 $3 \times 10^5$ 层）
• 查询只依赖于 $W_A, W_B, W_{LCA(A,B)}$

2. 博弈策略分析

• 双方轮流选择节点涂色
• 得分基于到各自目标节点的距离之和
• 最优策略下，差值可以通过数学公式计算

代码解析

分块初始化

B = sqrt(2 * n + 1), cnt = (2 * n + 1) / B;
for (int i = 1; i <= cnt; i++)
    L[i] = (i - 1) * B + 1, R[i] = i * B;

树结构预处理

nxt[n] = n;
for (int i = n - 1; i; i--) {
    nxt[i] = nxt[i + 1];
    if (a[i] % 2 == 0)
        nxt[i] = i, b[++CNT] = nxt[i + 1] - i;
}

// 计算子树大小和距离
sz[n] = 1;
for (int i = n - 1; i; i--)
    sz[i] = (1ll * sz[i + 1] * a[i] + 1) % mod, 
    dis[i] = 1ll * a[i] * (dis[i + 1] + sz[i + 1]) % mod;

主要计算逻辑

for (int i = 1; i <= q; i++) {
    cin >> Q[i].a >> Q[i].b >> Q[i].c, Q[i].id = i;
    // 基础得分计算
    ans[Q[i].id] = 1ll * (dis[Q[i].a] - dis[Q[i].b]) * inv % mod;
    
    if (OP)  // 奇偶性修正
        ans[Q[i].id] = (ans[Q[i].id] + 1ll * (Q[i].a + Q[i].b - 2 * Q[i].c) * inv) % mod;
    
    // 处理路径上的奇偶性影响
    vector<int> v1[2];
    // ... 复杂的路径分析逻辑
}

分块更新与查询

void change(int x) {
    // 更新分块内的标记和求和数组
    for (int i = L[bl[x]]; i <= R[bl[x]]; i++)
        res[i] = res[i] ^ tag[bl[x]][i & 1];
    
    // 更新奇偶位置的和
    sum[bl[x]][0] = sum1[R[bl[x]]][0], sum[bl[x]][1] = sum1[R[bl[x]]][1];
}

int solve(int x, int op) {
    // 查询分块信息
    if (!tag[bl[x]][op])
        return sum2[bl[x] - 1][op] + sum1[x][op];
    return sum2[bl[x] - 1][op] + len - sum1[x][op];
}

算法核心

1. 距离计算优化

通过预处理 $dis[i]$ 和 $sz[i]$ 数组，可以在 $O(1)$ 时间内计算任意两个节点的基础距离差值。

2. 奇偶性处理

由于游戏轮流进行，节点的选择顺序对结果有重要影响，需要通过奇偶性分析来修正。

3. 分块技术

将 $2n+1$ 的范围分块处理，每个块维护：

• 奇偶位置的标记 tag[i][0/1]
• 奇偶位置的和 sum[i][0/1]
• 前缀和 sum2[i][0/1]

复杂度分析

• 预处理：$O(n)$
• 每个查询：$O(\sqrt{n})$ 由于分块
• 总复杂度：$O(n + q\sqrt{n})$

关键技巧

1. 分块优化：将大规模查询分解为块内和块间处理
2. 奇偶性标记：利用位运算高效处理翻转操作
3. 前缀和数组：支持快速区间查询
4. 模运算处理：正确处理负数和取模