[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 × 根路径 $lca(u,v)$ "（根到 LCA 的边出现两次，要减掉两次）。
根路径加一 = 单点差分：给"根到 $x$ 的路径上每条边加一"，只需要在差分数组上 c[x] += 1。因为边 $(t, parent[t])$ 在根路径 $x$ 上当且仅当 $x \in subtree(t)$ ，所以"边值 = 子树的差分和"。

把三点合起来，P u v 退化成三个单点修改：

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

下面的表格演示样例中每次 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$ 完全一致。

于是最终做法是：倍增 LCA 预处理 + DFS 序 + Fenwick。P 只做三次单点加；Q 的"子树和"在 DFS 序上就是区间和 $\text{sum}(dfn[t], dfn[t]+sz[t]-1)$ ，由树状数组回答。

边差分与点差分

同样是"路径加一"，点差分和边差分的系数不同：

	点差分（路径上点的覆盖次数）	边差分（路径上边的覆盖次数）
单次 `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$ 是加法线性算子，所有 $S(t)$ 构成交换幺半群。
单点修改是"祖先前缀"自同态：c[x] += v 使 $S(t)$ 增加 $v$ 当且仅当 $t$ 是 $x$ 的祖先，即恰好是"根路径 $x$ 上的每条边加 $v$ "。因此"根路径加一"被压缩成一次单点修改。
路径是三条根路径的线性组合： $path(u,v) = rootpath(u) + rootpath(v) - 2 \cdot rootpath(lca)$ ，线性组合可以直接逐点相加，所以一次 P 只要三次修改。

代码

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157/**
 * 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
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int LOG = 20; // 2^20 > 1e6，本题 n <= 1e5，按模板保持 20

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

int depth[MAXN];        // depth[u] 表示节点 u 的深度
int up[MAXN][LOG + 1];  // up[u][j] 表示 u 的 2^j 级祖先
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;
}

// 预处理：按 BFS 顺序求父亲、深度，再倍增求 up[][j]。
// 用迭代写法，避免 10^5 深链上递归 DFS 撑爆系统栈。
void preprocess(int root) {
    vector<int> order; // BFS 访问顺序，父节点总在子节点之前
    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 == up[u][0]) continue; // 跳过父节点
            up[v][0] = u;
            depth[v] = depth[u] + 1;
            order.push_back(v);
        }
    }
    // 倍增转移：2^j 级祖先 = 先跳 2^(j-1)，再跳 2^(j-1)。
    for (int j = 1; j <= LOG; j++) {
        for (int i = 0; i < (int)order.size(); i++) {
            int u = order[i];
            up[u][j] = up[up[u][j - 1]][j - 1];
        }
    }
    // 子树大小：按 BFS 逆序向上累加。
    for (int i = 0; i < (int)order.size(); i++) {
        sz[order[i]] = 1;
    }
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        if (u != root) {
            sz[up[u][0]] += sz[u];
        }
    }
}

// 求节点 u 向上跳 k 层的祖先（k 拆成二进制位跳）。
int kth_ancestor(int u, int k) {
    for (int j = 0; j <= LOG; j++) {
        if (k & (1 << j)) {
            u = up[u][j];
        }
    }
    return u;
}

// 倍增求 a, b 的最近公共祖先。
int lca(int a, int b) {
    if (depth[a] < depth[b]) {
        swap(a, b);
    }
    a = kth_ancestor(a, depth[a] - depth[b]); // 先把深的点提到同一深度
    if (a == b) {
        return a;
    }
    for (int j = LOG; j >= 0; j--) {
        if (up[a][j] != up[b][j]) { // 还没跳过 LCA，可以一起跳
            a = up[a][j];
            b = up[b][j];
        }
    }
    return up[a][0]; // 最后停在 LCA 的两个儿子上
}

// 迭代栈求 DFS 序：保证每棵子树在 dfn 上是连续区间 [dfn[x], dfn[x] + sz[x] - 1]。
void dfs_order(int root) {
    vector<int> st;
    st.push_back(root);
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        timer++;
        dfn[u] = timer;
        for (int j = 0; j < (int)g[u].size(); j++) {
            int v = g[u][j];
            if (v != up[u][0]) {
                st.push_back(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);
    }

    preprocess(1);
    dfs_order(1);

    while (m--) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (op == 'P') {
            // 路径 u->v 上的每条边 +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 的差分和。
            int ans = bit_prefix(dfn[child] + sz[child] - 1) - bit_prefix(dfn[child] - 1);
            cout << ans << '\n';
        }
    }

    return 0;
}

复杂度

预处理：BFS 与 DFS 序 $O(n)$ ，倍增表 $O(n \log n)$ 。
单次操作：P 一次 LCA + 三次单点加，Q 两次前缀和，都是 $O(\log n)$ 。
总复杂度 $O((n+m) \log n)$ ，空间 $O(n \log n)$ （倍增表）。

总结

"树上路径加一、单边点查"的标准套路是树上边差分：把边权映射到子节点，把路径拆成三条根路径，于是路径操作变成三个点的差分，边查询变成子树和；再用 DFS 序把子树变成区间、用 Fenwick 在线维护。与"点差分"只在 LCA 处差一个系数（ $-2$ vs $-1$ 和 $parent(lca)$ ）。rbook 的《倍增求 LCA》讲解了本解使用的倍增模板（lca-binary-lifting），Fenwick 部分来自《树状数组：单点修改与区间查询》。仓库里另一种参考实现（main.py）用重链剖分拆路径，每次操作 $O(\log^2 n)$ ，也可行但常数和实现都更重。

图示解析

这张 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 + 边差分 + Fenwick（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 序如何把路径操作压成常数个单点修改”。核心是把二维的路径结构压成一维的差分点：一次 P 只动三个点，一次 Q 只查一个区间。