题解

算法分析

本题是一个 动态树分治（点分树） 问题，用于高效处理树上的动态查询和修改操作。属于 数据结构 中的 树分治 和 动态维护 问题。

问题本质

我们需要维护一棵带权树，支持：

1. 动态修改：在节点上增加或减少军队数量
2. 实时查询：找到最优补给站位置，使得 $\sum (d_v \cdot \text{dist}(u,v))$ 最小

核心思路

1. 构建点分树：

   • 通过不断寻找树的重心，构建一棵深度为 $O(\log n)$ 的分治树
   • 每个节点存储其在不同分治层中的信息

2. 信息维护：

   • sw[i]：存储分治块 $i$ 中的军队总数
   • need[i]：存储以分治中心为补给站时的总花费
   • p[x]：记录节点 $x$ 在各个分治层中的距离信息

3. 动态更新：

   • 当军队数量变化时，更新所有相关分治块的信息
   • 利用点分树的高效性，每个操作影响 $O(\log n)$ 个分治块

4. 查询最优解：

   • 在点分树上从根向下移动
   • 根据子树军队数量决定移动方向
   • 利用预计算的信息快速计算总花费

算法标签

• 点分治（树分治）
• 点分树（重心分治树）
• 动态树问题
• 树的重心分解

关键代码解析

// 寻找重心
void Find(int x, int fx) {
    sz[x] = 1;
    int mx = 0;
    for (auto [y, w] : g[x]) {
        if (!vis[y] && y != fx) {
            Find(y, x), sz[x] += sz[y];
            mx = max(mx, sz[y]);
        }
    }
    if (max(SZ - sz[x], mx) * 2 <= SZ) {
        root = x;
    }
}

// 构建点分树
int solve(int u) {
    if (SZ == 1) return u;
    root = 0, Find(u, 0), u = root, vis[u] = 1;
    
    for (auto &[v, w] : g[u]) {
        if (!vis[v]) {
            m++, SZ = 0, need[m] += 1ll * dfs(v, u, m, w) * w;
            int t = m;
            ed[u].push_back({t, solve(v), v, w});
        }
    }
    return u;
}

// 动态更新
void Add(int u, int k) {
    for (auto &[v, d] : p[u]) {
        sw[v] += k, need[v] += 1ll * k * d;
    }
}

// 查询最优解
void query(int u) {
    int center = 0;
    for (auto &e : ed[u]) {
        if (sw[e.son] * 2 > sum) {
            center = e.son;
        }
    }
    // 根据子树军队数量决定移动方向
    // ...
}

时间复杂度

• 点分树构建：$O(n \log n)$
• 每次更新操作：$O(\log n)$（影响 $O(\log n)$ 个分治块）
• 每次查询操作：$O(\log n)$（在点分树上移动）
• 总体复杂度：$O((n + Q) \log n)$，能够处理 $n, Q \leq 10^5$ 的数据规模

空间复杂度

• $O(n \log n)$，用于存储点分树结构和各层信息

算法优势

1. 高效动态维护：利用点分树的平衡性，每个操作只影响 $O(\log n)$ 个节点
2. 快速查询：通过预计算的信息，可以快速定位最优补给站
3. 支持在线操作：可以实时处理动态修改和查询

总结

本题通过构建点分树，将原树上的动态问题转化为分治结构上的高效维护，是点分治算法的经典应用。关键在于理解点分树的构建过程和信息维护方式，以及如何利用分治结构快速回答查询。