[USACO11DEC] Grass Planting G

形式化题目

给定一棵 $n$ 个节点的树, 每条边初始覆盖次数为 $0$ . 按顺序处理 $m$ 次操作:

P u v: 把 $u$ 到 $v$ 简单路径上的每条边覆盖次数加一;
Q u v: $u$ 、 $v$ 是一条边的两个端点, 回答这条边当前的覆盖次数.

要求在线回答所有查询(更新与询问交错出现).

思路

先看一个可以直接验证想法的朴素解:

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:30
 * update_at: 2026-08-12 22:30
 */
// brute.cpp：小数据暴力解，每条路径沿父链逐边 +1，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m;
vector<int> g[MAXN]; // 邻接表存树

int depth[MAXN];
int parent[MAXN];    // parent[x] 表示 x 的父节点，边 (x, parent[x]) 由 x 代表
int edge_val[MAXN];  // edge_val[x] 表示边 (x, parent[x]) 被覆盖的次数

// 朴素 BFS 求父节点与深度。
void build_tree(int root) {
    vector<int> order;
    order.push_back(root);
    depth[root] = 1;
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int j = 0; j < (int)g[u].size(); j++) {
            int v = g[u][j];
            if (v == parent[u]) {
                continue;
            }
            parent[v] = u;
            depth[v] = depth[u] + 1;
            order.push_back(v);
        }
    }
}

// 朴素 LCA：两个点交替沿父链一步一步向上爬。
int naive_lca(int a, int b) {
    while (depth[a] > depth[b]) {
        a = parent[a];
    }
    while (depth[b] > depth[a]) {
        b = parent[b];
    }
    while (a != b) {
        a = parent[a];
        b = parent[b];
    }
    return a;
}

// 路径 u->v 上的每条边 +1：从 u 爬到 lca，再从 v 爬到 lca，逐边加一。
void path_add(int u, int v) {
    int c = naive_lca(u, v);
    while (u != c) {
        edge_val[u]++; // 边 (u, parent[u]) 在路径上
        u = parent[u];
    }
    while (v != c) {
        edge_val[v]++;
        v = parent[v];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    build_tree(1);

    while (m--) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (op == 'P') {
            path_add(a, b);
        } else {
            // Q：a、b 是一条边的两个端点，深的一端代表这条边。
            int child = (depth[a] > depth[b]) ? a : b;
            cout << edge_val[child] << '\n';
        }
    }

    return 0;
}

brute.cpp 把每条边 $(x, parent[x])$ 的值挂在深端点 $x$ 上: P 从 $u$ 、 $v$ 分别沿父链爬到 lca, 逐边 +1; Q 直接输出深端点的值. 单次操作 $O(\text{路径长})$ , 最坏 $O(n)$ , $10^5$ 数据不可行.

解决本题的关键观察有三步:

边权挂到深端点: 每条边 $(x, parent[x])$ 用较深的子节点 $x$ 代表, 回答 Q u v 就是查 $w(deep(u,v))$ .
路径拆成三条根路径: $u$ 到 $v$ 的路径边集等于"根到 $u$ 路径 + 根到 $v$ 路径 − $2 \times$ 根到 $lca(u,v)$ 路径"(根到 LCA 的边出现两次, 必须全部扣除).
根路径加一对应单点差分: 给"根到 $x$ 路径上的每条边加一", 只需要在差分数组上做 c[x] += 1. 因为边 $(t, parent[t])$ 位于根到 $x$ 的路径上当且仅当 $x \in subtree(t)$ , 所以一条边的实际权值等于其子节点子树内差分值的总和(怎么把"子树和"快速取出来, 见后面的 DFS 序一节).

图解：边权映射与路径差分容斥

下面的图展示了样例树上边权映射到子节点的结构, 以及路径边差分在 LCA 处消除多余影响的原理:

graph TD
    subgraph S1["边权挂到子节点(样例树)"]
        direction TB
        1((1: 根)) -->|"边 (1,4)<br/>挂在点 4"| 4((4))
        4 -->|"边 (2,4)<br/>挂在点 2"| 2((2))
        4 -->|"边 (3,4)<br/>挂在点 3"| 3((3))
    end

    subgraph S2["路径差分容斥原理"]
        direction TB
        R((根节点)) -.->|"上方边: +1 + 1 - 2 = 0"| P_LCA((...))
        P_LCA -.->|"边 (lca, fa): +1 + 1 - 2 = 0"| LCA(("LCA (c -= 2)"))
        LCA ==>|"路径边: 仅 u 贡献 +1"| U_ANC((...))
        U_ANC ==>|"路径边: 仅 u 贡献 +1"| U(("u (c += 1)"))
        LCA ==>|"路径边: 仅 v 贡献 +1"| V_ANC((...))
        V_ANC ==>|"路径边: 仅 v 贡献 +1"| V(("v (c += 1)"))
    end

观察「边权挂到子节点」那幅图, 每条树边唯一对应深度更深的那个子节点, 查询边 $(u,v)$ 时只需定位深度较大的端点. 观察「路径差分容斥原理」那幅图, $c[u] \mathrel{+}= 1$ 和 $c[v] \mathrel{+}= 1$ 分别使从根到 $u$ 与从根到 $v$ 上的所有边增量为 1. 但 LCA 上方的祖先边不属于 $u \to v$ 的路径, 却被两端同时覆盖了两次; 因此在 $lca$ 处执行 $c[lca] \mathrel{-}= 2$ , 恰好使所有 LCA 及上方边的子树和净增量变为 $1 + 1 - 2 = 0$ , 从而仅保留了 $u \to v$ 简单路径上的修改.

把这三点合起来, 一次 P u v 操作完全退化为三个单点修改:

c[u] += 1,\quad c[v] += 1,\quad c[lca(u,v)] -= 2

该公式表示给 $u$ 和 $v$ 的祖先链增加一次计数, 并通过在 $lca$ 处扣除两次计数来精确截断对 LCA 及其上方祖先边的影响.

下面的表格演示样例中每次 P 之后差分数组 $c[]$ 的变化(树以 1 为根: 1-4、2-4、3-4, 节点 4 比 1 深), 以及 Q 如何用子树和回答:

操作	$c[1]$	$c[2]$	$c[3]$	$c[4]$	输出
初始	0	0	0	0
P 2 3	0	1	1	-2
P 1 3	-1	1	2	-2
Q 3 4					2(= $c[3]$ )
P 1 4	-2	1	2	-1
Q 2 4					1(= $c[2]$ )
Q 1 4					2(= $c[2]+c[3]+c[4]$ )

观察第二行: P 2 3 的 LCA 是 4, 所以 $c[4]$ 变成 $-2$ . Q 3 4 回答边 $(3,4)$ , 就是子树 $\{3\}$ 的差分和 $c[3] = 2$ ; Q 1 4 回答边 $(1,4)$ , 即子树 $\{2,3,4\}$ 的和 $1+2-1 = 2$ . 这与样例输出 $2,1,2$ 完全一致.

DFS 序：把「子树和」变成「区间和」

到这里还剩一个麻烦: Q 要的是"节点 $t$ 的子树内所有差分值之和", 直接做就得把整棵子树遍历一遍; 而 P 又会不断修改单点, 两种操作交错出现. 需要一种能一次性取出子树和、又能跟着修改走的表示.

做法是给每个点打一个 DFS 时间戳: 从根开始深搜, 第一次访问节点 $t$ 时记 dfn[t] = ++timer.

关键性质是: 以 $t$ 为根的子树, 在这套编号下恰好占一段连续区间 $[dfn[t],\, dfn[t] + sz[t] - 1]$ , 其中 $sz[t]$ 是 $t$ 的子树大小. 原因是深搜一旦进入 $t$ , 就会把 $t$ 的整棵子树走完才会退出, 中途不可能跑去访问子树外的点; 而子树外的点要么在进入 $t$ 之前就已经访问完, 要么得等 $t$ 这一支返回之后才轮到. 所以这段区间里的点不多不少, 正好是 $t$ 的子树.

于是 Q u v 变成: 取出这条边的深端点 child, 在 DFS 序上查区间 $[dfn[child],\, dfn[child]+sz[child]-1]$ 的和. 「子树和」这个树上的量, 就这样变成了数组上的「区间和」, 问题从树上落回了一维数组.

于是最终做法是: 倍增 LCA 预处理 + DFS 序 + 树状数组(Fenwick). P 只做三次单点加; Q 的"子树和"在 DFS 序上对应连续区间和 $\text{sum}(dfn[t], dfn[t]+sz[t]-1)$ , 由树状数组高效回答.

为什么用树状数组而不是普通前缀和: P 与 Q 交错出现, 数组随时在变. 普通前缀和数组一旦遇到单点修改, 所有靠后的前缀都要重算, 单次退化成 $O(n)$ ; 树状数组把「单点加」和「前缀和查询」都做成 $O(\log n)$ , 区间和再用两次前缀和相减, 正好对上本题的三类操作.

边差分与点差分

同样是"树上路径加一", 点差分与边差分的系数有着本质不同:

	点差分(路径上点的覆盖次数)	边差分(路径上边的覆盖次数)
单次 `P u v`	$c[u]{+}{+},\ c[v]{+}{+},\ c[lca]{-}{-},\ c[parent(lca)]{-}{-}$	$c[u]{+}{+},\ c[v]{+}{+},\ c[lca] -= 2$
恢复方式	点 $t$ 的值 = $subtree(t)$ 的差分和	边 $(t, parent[t])$ 的值 = $subtree(t)$ 的差分和

原因在于: 根路径 $u$ 与根路径 $v$ 的点集里 LCA 出现了两次, 路径点集本身需要包含 LCA, 因此减一次 LCA、再减一次 $parent(lca)$ , 使 LCA 处的净贡献保留为 $2 - 1 = 1$ ; 而路径边集完全不包含边 $(lca, parent(lca))$ , 所以在 LCA 处两次多余的贡献必须全部扣除, 即执行 c[lca] -= 2.

线性叠加原理

为什么多次路径修改后依然可以用子树和还原答案:

子树求和满足加法线性: 子树和 $S(t) = \sum_{y \in subtree(t)} c[y]$ 具有完全的可加性, 每个单点差分值的修改对所有祖先的子树和贡献互相独立.
单点差分等价于祖先链前缀更新: 在差分数组中执行 c[x] += v, 会使得所有包含 $x$ 的子树(即 $x$ 的所有祖先节点 $t$ )的子树和 $S(t)$ 恰好增加 $v$ . 这正好对应将根到 $x$ 路径上的所有边权增加 $v$ .
路径操作由根路径线性组合得到: 简单路径 $path(u,v) = rootpath(u) + rootpath(v) - 2 \cdot rootpath(lca)$ , 这一线性组合使得每次路径修改只需常数次单点更新即可准确表达.

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:30
 * update_at: 2026-10-26 22:32
 */
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;  // 本题 n <= 1e5
const int max_log = 20;   // 2^17 > 1e5，留一点余量

using Graph = vector<int>;
Graph tree[maxn];

int n, m, lg;           // lg = 实际需要的二进制位数，按 n 收紧，不做无用功
int depth[maxn];        // depth[0] = 0，根 depth = 1；0 号点当哨兵
int up[maxn][max_log];  // up[u][j] = u 的 2^j 级祖先，越界一律落到 0

int dfn[maxn];  // dfn[u] 是 u 的 DFS 序
int sz[maxn];   // sz[u] 是 u 的子树大小
int timer;      // DFS 序计时器

int bit[maxn];  // 差分数组 c[] 的树状数组（单点加、前缀和）

// 树状数组：位置 pos 加上 value。
void bit_add(int pos, int value) {
    for (int i = pos; i <= n; i += i & -i) {
        bit[i] += value;
    }
}

// 树状数组：求差分数组 [1, pos] 的前缀和。
int bit_prefix(int pos) {
    int res = 0;
    for (int i = pos; i > 0; i -= i & -i) {
        res += bit[i];
    }
    return res;
}

// 递归 DFS：进点时就填好 depth 和 up[u][1..lg-1]。
// 走到 u 时父亲的整行已经算完，所以 u 的 2^j 级祖先可以直接拿来拼。
// 本题另外在进点时打 dfn 时间戳、回溯时累加 sz，供子树和查询使用。
void dfs(int u, int fa) {
    depth[u] = depth[fa] + 1;  // fa 为 0 时正好得到根 depth = 1
    up[u][0] = fa;
    for (int j = 1; j < lg; ++j) {
        up[u][j] = up[up[u][j - 1]][j - 1];  // 先跳 2^(j-1)，再跳 2^(j-1)
    }

    dfn[u] = ++timer;  // 进点先后就是先序，子树因此落在连续区间里
    sz[u] = 1;
    for (int v : tree[u]) {
        if (v == fa) continue;  // 只跳过父亲，其余都是儿子
        dfs(v, u);
        sz[u] += sz[v];  // 回溯时把子树的点并进来
    }
}

// 预处理：清空上一组的残留，再从 root 递归灌满 depth 与 up。
// 多测时每组都要重新调用，否则会读到上一张图的祖先表。
void init_lca(int n_, int root = 1) {
    n = n_;
    lg = 0;
    while ((1 << lg) <= n) ++lg;  // 最长上跳 n-1 层，只用到前 lg 位
    for (int u = 0; u <= n; ++u) {
        depth[u] = 0;
        for (int j = 0; j < lg; ++j) up[u][j] = 0;
    }
    timer = 0;      // dfn 与 sz 也跟着本组重来
    dfs(root, 0);   // 哨兵点 0：depth[0] = 0、up[0][*] = 0，越界都落到这里
}

// u 的第 k 级祖先：k 的二进制里每个 1 位跳一次
int kth_ancestor(int u, int k) {
    for (int j = 0; j < lg; ++j) {
        if ((k >> j) & 1) u = up[u][j];
    }
    return u;
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);       // 让 a 是较深的点
    a = kth_ancestor(a, depth[a] - depth[b]);  // 先跳到同一层
    if (a == b) return a;                      // 已经重合，b 就是答案

    // 从大步到小步：跳到 LCA 的正下方，父节点就是答案
    for (int j = lg - 1; j >= 0; --j) {
        if (up[a][j] != up[b][j]) {
            a = up[a][j];
            b = up[b][j];
        }
    }
    return up[a][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    init_lca(n, 1);  // n 个点、以 1 为根：深度、倍增表、DFS 序、子树大小一次 DFS 全就位

    while (m--) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (op == 'P') {
            // 路径 a->b 上的每条边 +1，转成三个点的边差分。
            int c = lca(a, b);
            bit_add(dfn[a], 1);
            bit_add(dfn[b], 1);
            bit_add(dfn[c], -2);
        } else {
            // Q：a、b 是一条边的两个端点，深的那一端代表这条边。
            int child = (depth[a] > depth[b]) ? a : b;
            // 边 (child, parent[child]) 的值 = 子树 child 的差分和，
            // 也就是 DFS 序上区间 [dfn[child], dfn[child] + sz[child] - 1] 的和。
            int ans = bit_prefix(dfn[child] + sz[child] - 1) - bit_prefix(dfn[child] - 1);
            cout << ans << '\n';
        }
    }

    return 0;
}

复杂度

预处理: 一次 DFS 同时求出深度、DFS 序与子树大小, 这部分是 $O(n)$ ; 顺带推的倍增表是 $O(n \log n)$ .
单次操作: P 操作为一次 LCA 查询加三次单点加, Q 操作为两次前缀和求区间和, 均为 $O(\log n)$ .
总时空复杂度: 时间为 $O((n+m) \log n)$ , 空间为 $O(n \log n)$ (倍增表).

总结

"树上路径加一、单边点查"的标准模式是树上边差分:

将无向边权映射到深度较深的子节点点权;
将路径修改拆解为两条到根路径与一条 LCA 路径的容斥, 从而转化为三个单点的差分修改;
利用 DFS 序将子树在空间上展开为连续区间, 配合树状数组实现在线动态修改与单点(单边)子树和查询.

与点差分相比, 边差分仅在 LCA 处差一个系数( $-2$ 对比 $-1$ 与 $parent(lca)$ 处的 $-1$ ).

图示解析

下面用 ASCII 流程图总结整道题从暴力模拟到边差分的推导路线:

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17朴素模拟(brute.cpp)
  边 (x, parent[x]) 挂在深端点 x 上, P 沿父链逐边 +1       O(路径长) 每次
        |
        | 瓶颈: 更新与查询都按"路径"发生, 最坏 O(n)
        v
关键观察
  1. 路径 u..v = 根路径 u + 根路径 v - 2 * 根路径 lca
  2. "根路径 x 每条边加 1" = 差分数组 c[x] += 1(子树和恢复边值)
  3. DFS 序把子树变成连续区间
        |
        v
LCA + 边差分 + 树状数组(main.cpp)
  P u v: 三次单点加 c[u]+1、c[v]+1、c[lca]-2
  Q u v: 子树区间和 sum(dfn[child], dfn[child]+sz[child]-1)
        |
        v
复杂度 O((n + m) log n), 空间 O(n log n)

图中三条主线对应"暴力瓶颈在哪"、“路径如何拆成根路径的线性组合"以及"差分配合 DFS 序如何将二维路径操作降维成一维区间求和”. 核心在于将树上路径的二维拓扑更新映射为一维数组上的单点差分与连续区间和查询.