NekoNowcoder

Appearance

ANationalPandemic - 题解 ​

标签与难度 ​

标签: 树链剖分, 线段树, LCA, 树上路径操作, 数据结构, 公式推导 难度: 2200

题目大意喵~ ​

喵哈~！各位算法大师们，今天我们来解决一个关于国家疫情控制的有趣问题！(ฅ'ω'ฅ)

在一个由 n 个城市和 n-1 条道路构成的国家里（是的，它是一棵树！），每个城市 x 都有一个疫情严重度 F(x)，初始都为0。我们需要处理三种事件：

  1. 爆发 (Outbreak): 城市 x 爆发疫情，严重值为 w。这会导致所有城市 y 的严重度 F(y) 增加 w - dist(x, y)。这里的 dist(x, y) 是城市 x 和 y 之间路径上的边数。
  2. 控制 (Control): 城市 x 的情况得到控制，F(x) 更新为 min(F(x), 0)。也就是说，如果 F(x) 是正数，就把它清零；如果是负数或零，就保持不变。
  3. 查询 (Query): 查询城市 x 当前的严重度 F(x)。

我们需要处理 m 次这样的事件，并且要快准狠地完成任务，喵~

解题思路分析 ​

这道题最棘手的地方就是操作1，它是一个对整棵树的全局更新，而且更新的值还和每个点到爆发点 x 的距离有关。如果每次都遍历所有 n 个点来更新，那肯定会超时啦~ 所以我们需要找到更聪明的办法，喵！

优雅地拆解公式 ​

首先，我们来分析一下操作1的更新公式：F_new(y) = F_old(y) + w - dist(x, y)。

如果有很多次爆发，比如 k 次，分别是 (x_1, w_1), (x_2, w_2), ..., (x_k, w_k)，那么一个城市 y 的总严重度（先不考虑操作2）就是所有这些更新的和：

F(y)=∑i=1k(wi−dist(xi,y))F(y) = \sum_{i=1}^{k} (w_i - \text{dist}(x_i, y))

在树上，两个点 u 和 v 的距离有一个非常经典的公式，它和它们的深度以及最近公共祖先（LCA）有关。我们先指定一个根节点（比如节点1），然后定义 dep(u) 为节点 u 的深度（根节点深度为1）。那么：

dist(u,v)=dep(u)+dep(v)−2⋅dep(lca(u,v))\text{dist}(u, v) = \text{dep}(u) + \text{dep}(v) - 2 \cdot \text{dep}(\text{lca}(u, v))

把这个公式代入我们的 F(y) 表达式里：

F(y)=∑i=1k(wi−(dep(xi)+dep(y)−2⋅dep(lca(xi,y))))F(y) = \sum_{i=1}^{k} (w_i - (\text{dep}(x_i) + \text{dep}(y) - 2 \cdot \text{dep}(\text{lca}(x_i, y))))

现在，我们施展一点代数魔法，把这个和式拆开，重新组合一下：

F(y)=(∑i=1k(wi−dep(xi)))−(∑i=1k1)⋅dep(y)+2⋅(∑i=1kdep(lca(xi,y)))F(y) = \left( \sum_{i=1}^{k} (w_i - \text{dep}(x_i)) \right) - \left( \sum_{i=1}^{k} 1 \right) \cdot \text{dep}(y) + 2 \cdot \left( \sum_{i=1}^{k} \text{dep}(\text{lca}(x_i, y)) \right)

看呐！这个复杂的式子被我们分成了三个部分：

  1. Part A: ∑i=1k(wi−dep(xi))\sum_{i=1}^{k} (w_i - \text{dep}(x_i))。这个部分只和爆发点 x_i 有关，和我们查询的点 y 完全没关系！我们可以用一个全局变量 global_sum 来维护这个和。每次有新的爆发 (x, w)，我们就让 global_sum += w - dep(x)。
  2. Part B: (∑i=1k1)⋅dep(y)(\sum_{i=1}^{k} 1) \cdot \text{dep}(y)。∑1\sum 1 就是总的爆发次数嘛！我们也可以用一个全局变量 outbreak_count 来记录。所以这部分就是 outbreak_count * dep(y)。
  3. Part C: 2⋅∑i=1kdep(lca(xi,y))2 \cdot \sum_{i=1}^{k} \text{dep}(\text{lca}(x_i, y))。这部分是真正的挑战，它同时和所有爆发点 x_i 以及查询点 y 相关。

解决核心难题 (Part C) ​

怎么高效计算 ∑i=1kdep(lca(xi,y))\sum_{i=1}^{k} \text{dep}(\text{lca}(x_i, y)) 呢？直接计算还是很困难。这里就需要一个非常巧妙的转换了，喵~

我们换个角度想。我们可以在树上维护一些信息。对于每一次爆发 x_i，我们对从根节点到 x_i 的路径上所有节点的值都增加1。我们用一个数据结构（比如线段树）来维护每个节点上的这个值，记作 T(v)。

现在，如果我们想查询点 y 的 ∑i=1kdep(lca(xi,y))\sum_{i=1}^{k} \text{dep}(\text{lca}(x_i, y))，可以试试计算从根节点到 y 的路径上所有节点 v 的 T(v) 值的和，即 ∑v∈path(root,y)T(v)\sum_{v \in \text{path}(root, y)} T(v)。

这个路径和等于什么呢？我们来展开看看：

∑v∈path(root,y)T(v)=∑v∈path(root,y)(∑i=1k[v∈path(root,xi)])\sum_{v \in \text{path}(root, y)} T(v) = \sum_{v \in \text{path}(root, y)} \left( \sum_{i=1}^{k} [v \in \text{path}(root, x_i)] \right)

这里的 [...] 是艾弗森括号，如果条件为真则为1，否则为0。

交换一下求和顺序：

=∑i=1k(∑v∈path(root,y)[v∈path(root,xi)])= \sum_{i=1}^{k} \left( \sum_{v \in \text{path}(root, y)} [v \in \text{path}(root, x_i)] \right)

里面的那个和式 ∑v∈path(root,y)[v∈path(root,xi)]\sum_{v \in \text{path}(root, y)} [v \in \text{path}(root, x_i)] 算的是什么呢？它计算的是同时在 path(root, y) 和 path(root, x_i) 两条路径上的节点 v 的数量。因为两条路径都从根开始，所以它们的交集就是从根到它们LCA的路径，即 path(root, lca(x_i, y))。

路径 path(root, u) 上的节点数量正好是 dep(u)（当根深度为1时）。所以：

∑v∈path(root,y)T(v)=∑i=1kdep(lca(xi,y))\sum_{v \in \text{path}(root, y)} T(v) = \sum_{i=1}^{k} \text{dep}(\text{lca}(x_i, y))

Bingo！我们成功地把那个复杂的LCA求和转换成了一个路径求和问题！

整合方案 ​

树上的路径修改和路径查询，这不就是树链剖分（Heavy-Light Decomposition）加线段树的经典应用场景嘛！

所以我们的完整方案就是：

  1. 预处理:

    • 先用两次DFS对树进行树链剖分，得到每个节点的深度dep、父节点fa、重儿子son、所在链的顶部top、以及它在线段树中的位置dfn。
    • 建立一棵线段树，所有初始值为0。

  2. 处理操作1 (x, w):

    • 更新全局变量：global_sum += w - dep[x]，outbreak_count++。
    • 利用树链剖分，对根节点到 x 的路径上的所有节点，在线段树中对应区间的值都加上 2。（因为Part C的公式里有个系数2）。

  3. 处理操作3 (y):

    • 利用树链剖分，查询根节点到 y 的路径上所有节点的权值和，记为 path_sum。
    • 不考虑操作2的 F(y) 值为：global_sum - outbreak_count * dep[y] + path_sum。
    • 我们还需要一个 adjustments 数组来记录操作2带来的点修改。所以最终结果是 F(y) + adjustments[y]。

  4. 处理操作2 (x):

    • 先按照操作3的方法计算出 x 当前的 F(x) 值。
    • 如果 F(x) > 0，我们就需要把它减掉。这个差值 -F(x) 就是对 x 的一个局部调整。我们把它加到 adjustments[x] 上：adjustments[x] -= F(x)。这样下次查询 x 时，这个调整就会被算进去啦。

这样，我们就能在 O(log⁡2N)O(\log^2 N) 的时间内处理每次操作，完美解决问题，喵呜~

代码实现 ​

这是我根据上面的思路，精心重构的一份代码，加满了注释，希望能帮助你理解哦~

cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 50010;
typedef long long ll;

// --- 图的表示 ---
vector<int> adj[MAXN];
int n;

// --- 树链剖分所需数组 ---
int parent[MAXN];      // 父节点
int depth[MAXN];       // 深度
int size[MAXN];        // 子树大小
int heavy_son[MAXN];   // 重儿子
int top_chain[MAXN];   // 所在重链的顶部节点
int dfn[MAXN];         // DFS序（在线段树中的位置）
int rev_dfn[MAXN];     // DFS序的反向映射
int timestamp;

// --- 线段树所需结构体和数组 ---
struct Node {
    ll sum;
    ll lazy;
} seg_tree[MAXN * 4];

// --- 全局变量和局部调整 ---
ll global_sum;       // 对应公式中的 Part A
ll outbreak_count;   // 对应公式中的 Part B
ll adjustments[MAXN]; // 对应操作2的局部调整

// --- DFS1: 计算深度、父节点、子树大小、重儿子 ---
void dfs1(int u, int p, int d) {
    parent[u] = p;
    depth[u] = d;
    size[u] = 1;
    heavy_son[u] = 0;
    int max_size = 0;

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs1(v, u, d + 1);
        size[u] += size[v];
        if (size[v] > max_size) {
            max_size = size[v];
            heavy_son[u] = v;
        }
    }
}

// --- DFS2: 剖分重链，计算DFS序 ---
void dfs2(int u, int top) {
    top_chain[u] = top;
    timestamp++;
    dfn[u] = timestamp;
    rev_dfn[timestamp] = u;

    if (heavy_son[u]) {
        dfs2(heavy_son[u], top);
    }

    for (int v : adj[u]) {
        if (v == parent[u] || v == heavy_son[u]) continue;
        dfs2(v, v); // v是新链的顶部
    }
}

// --- 线段树操作 ---
void push_up(int p) {
    seg_tree[p].sum = seg_tree[p * 2].sum + seg_tree[p * 2 + 1].sum;
}

void push_down(int p, int l, int r) {
    if (seg_tree[p].lazy != 0) {
        int mid = l + (r - l) / 2;
        seg_tree[p * 2].sum += seg_tree[p].lazy * (mid - l + 1);
        seg_tree[p * 2].lazy += seg_tree[p].lazy;
        seg_tree[p * 2 + 1].sum += seg_tree[p].lazy * (r - mid);
        seg_tree[p * 2 + 1].lazy += seg_tree[p].lazy;
        seg_tree[p].lazy = 0;
    }
}

void build(int p, int l, int r) {
    seg_tree[p].sum = 0;
    seg_tree[p].lazy = 0;
    if (l == r) return;
    int mid = l + (r - l) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
}

void update_range(int p, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        seg_tree[p].sum += (ll)val * (r - l + 1);
        seg_tree[p].lazy += val;
        return;
    }
    push_down(p, l, r);
    int mid = l + (r - l) / 2;
    if (ql <= mid) {
        update_range(p * 2, l, mid, ql, qr, val);
    }
    if (qr > mid) {
        update_range(p * 2 + 1, mid + 1, r, ql, qr, val);
    }
    push_up(p);
}

ll query_range(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return seg_tree[p].sum;
    }
    push_down(p, l, r);
    ll res = 0;
    int mid = l + (r - l) / 2;
    if (ql <= mid) {
        res += query_range(p * 2, l, mid, ql, qr);
    }
    if (qr > mid) {
        res += query_range(p * 2 + 1, mid + 1, r, ql, qr);
    }
    return res;
}

// --- 树链剖分路径操作 ---
void update_path(int u, int v, int val) {
    while (top_chain[u] != top_chain[v]) {
        if (depth[top_chain[u]] < depth[top_chain[v]]) swap(u, v);
        update_range(1, 1, n, dfn[top_chain[u]], dfn[u], val);
        u = parent[top_chain[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    update_range(1, 1, n, dfn[u], dfn[v], val);
}

ll query_path(int u, int v) {
    ll res = 0;
    while (top_chain[u] != top_chain[v]) {
        if (depth[top_chain[u]] < depth[top_chain[v]]) swap(u, v);
        res += query_range(1, 1, n, dfn[top_chain[u]], dfn[u]);
        u = parent[top_chain[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    res += query_range(1, 1, n, dfn[u], dfn[v]);
    return res;
}

// --- 初始化所有数据 ---
void init() {
    for (int i = 1; i <= n; ++i) {
        adj[i].clear();
        adjustments[i] = 0;
    }
    timestamp = 0;
    global_sum = 0;
    outbreak_count = 0;
}

void solve() {
    int m;
    cin >> n >> m;
    init();

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

    // 预处理
    dfs1(1, 0, 1);
    dfs2(1, 1);
    build(1, 1, n);

    for (int i = 0; i < m; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int x, w;
            cin >> x >> w;
            global_sum += (ll)w - depth[x];
            outbreak_count++;
            update_path(1, x, 2);
        } else if (type == 2) {
            int x;
            cin >> x;
            ll path_val = query_path(1, x);
            ll current_f = global_sum - outbreak_count * depth[x] + path_val + adjustments[x];
            if (current_f > 0) {
                adjustments[x] -= current_f;
            }
        } else { // type == 3
            int x;
            cin >> x;
            ll path_val = query_path(1, x);
            ll final_f = global_sum - outbreak_count * depth[x] + path_val + adjustments[x];
            cout << final_f << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(N+Mlog⁡2N)O(N + M \log^2 N)

    • 预处理（两次DFS进行树链剖分）需要 O(N)O(N) 的时间。
    • 构建线段树需要 O(N)O(N)。
    • 每次操作1或3，我们都需要进行一次树上路径操作。树链剖分将路径拆分成 O(log⁡N)O(\log N) 条重链上的连续区间，每次对线段树区间的操作是 O(log⁡N)O(\log N)，所以总的是 O(log⁡2N)O(\log^2 N)。
    • 操作2也需要查询一次，也是 O(log⁡2N)O(\log^2 N)。
    • 总共有 MM 次查询，所以查询部分总复杂度是 O(Mlog⁡2N)O(M \log^2 N)。

  • 空间复杂度: O(N)O(N)

    • 邻接表、树链剖分所需的各种数组、以及线段树（大小为 4N4N）都需要 O(N)O(N) 的空间。

知识点总结 ​

这道题是一个非常棒的练习题，融合了多种算法思想，喵~

  1. 公式推导与转换: 解决问题的关键在于将复杂的全局更新公式 w - dist(x, y) 转换成可以分块处理的形式。这是解决许多树上难题的第一步。
  2. 树链剖分: 当你遇到树上路径修改和路径查询时，树链剖分是一个非常强大的工具。它能将树上问题转化为序列问题，然后用线段树等数据结构高效解决。
  3. 线段树: 经典的数据结构，用于处理区间修改和区间查询。在这里，我们用它来维护树链剖分后的序列。
  4. 全局与局部思想: 我们将更新效果分为全局累加的量（global_sum, outbreak_count）、需要数据结构维护的半全局量（Part C）和纯粹的局部调整（adjustments数组）。这种分而治之的思想在处理复杂问题时非常有效！

希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦，喵~ (´｡• ᵕ •｡`) ♡