[USACO19DEC] Milk Visits S

根路径 G 前缀和配合倍增 LCA 容斥，O(log n) 回答路径上是否出现指定品种。

OJ: luogu

题目 ID: P5836

难度:普及

标签:LCA倍增前缀和树USACO

日期: 2026-07-17 02:00

形式化题目

给定一棵 $N$ 个节点的树，每个节点有颜色 G 或 H。有 $M$ 次询问，每次给定两个端点 $a$ 、 $b$ 和一种颜色 $C$ ，问树上的唯一简单路径 $a \to b$ （含端点）上是否存在颜色为 $C$ 的节点。依次输出每个询问的答案：存在输出 1，否则输出 0。

思路

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

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/**
 * 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:58
 * update_at: 2026-08-12 22:58
 */
// brute.cpp：小数据暴力解，每次查询沿路径 DFS 找路并统计颜色，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m;
char color[MAXN];       // color[i] 为 'G' 或 'H'
vector<int> g[MAXN];    // 树的邻接表
int path[MAXN];         // 记录当前 DFS 找到的路径节点
int path_len;           // 当前路径长度
bool vis[MAXN];         // 标记节点是否被访问
bool found;             // 是否已经找到目标节点

// 从 u 出发寻找 target，把路径存入 path[]；每一步选择往哪个邻居走。
void dfs_find(int u, int target) {
    vis[u] = true;
    path[path_len++] = u;
    if (u == target) {
        found = true;
        return;
    }
    for (int v : g[u]) {
        if (vis[v] || found) continue;
        dfs_find(v, target);
        if (found) return;
    }
    path_len--; // 回溯：这条路不通，撤销这个节点
}

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

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

    string ans;
    for (int i = 1; i <= m; i++) {
        int a, b;
        char want;
        cin >> a >> b >> want;

        // 每次查询都重新 DFS 找 a 到 b 的路径，复杂度 O(n)。
        memset(vis, 0, sizeof(vis));
        path_len = 0;
        found = false;
        dfs_find(a, b);

        // 统计路径上 G 的数量，H 的数量用总长度减 G 的数量补出。
        int cntG = 0;
        for (int j = 0; j < path_len; j++)
            if (color[path[j]] == 'G') cntG++;
        int cntH = path_len - cntG;

        if (want == 'G')
            ans.push_back(cntG > 0 ? '1' : '0');
        else
            ans.push_back(cntH > 0 ? '1' : '0');
    }
    cout << ans << '\n';

    return 0;
}

brute.cpp 对每次询问从 $a$ 出发沿树 DFS 找通向 $b$ 的唯一路径，再逐点统计 G 的个数：单次询问 $O(N)$ ，总复杂度 $O(NM)$ ，在 $10^5$ 的数据上不可行。

关键观察：只数一种颜色，剩下的用路径长度补。以 1 为根，预处理每个节点到根路径上 G 的数量 sumG[i]，那么任意路径 $a \to b$ 上 G 的数量可以容斥得到：

\mathrm{cntG} = \mathrm{sumG}(a) + \mathrm{sumG}(b) - 2 \cdot \mathrm{sumG}(\mathrm{lca}(a,b)) + [\mathrm{color}(\mathrm{lca}) = G]

路径上的点数 $\mathrm{len} = \mathrm{depth}(a) + \mathrm{depth}(b) - 2 \cdot \mathrm{depth}(\mathrm{lca}) + 1$ ，于是 $\mathrm{cntH} = \mathrm{len} - \mathrm{cntG}$ 。回答询问时，看目标品种的计数是否大于 0 即可。

这句话的几何含义：路径 $a \to b$ 等于"根到 $a$ 的路径"和"根到 $b$ 的路径"的并集去掉公共前缀"根到 LCA"，再把被减了两次的 LCA 补回来。用样例树（颜色串 HHGHG，边 1-2、2-3、2-4、1-5）验证一条询问：

text

1
2
3
4
5
6
7
8
9
10
11       1 (H)
      / \
    2 (H) 5 (G)
   / \
 3 (G) 4 (H)

询问 1 -> 4，喜欢 H：路径是 1 2 4，三个节点全是 H
sumG(1) = 0    sumG(4) = 0    lca(1,4) = 1
cntG = sumG(1) + sumG(4) - 2*sumG(1) + [color(1)=G] = 0
len = depth(1) + depth(4) - 2*depth(1) + 1 = 1 + 3 - 2 + 1 = 3
cntH = len - cntG = 3 > 0   ->  输出 1（样例第一位的 `1`）

再看两个退化情况验证公式的鲁棒性：询问 1 3 G 时 LCA 仍是 1，cntG = sumG(3) = 1 > 0，输出 1；询问 5 5 H 时路径只有节点 5 自己（它是 G），cntH = 1 - 1 = 0，输出 0，正好对应样例输出 10110 的最后一位。可见当 LCA 恰是某个端点、甚至 $a = b$ 时，公式无需特判。

实现上，一次 BFS 就能同时求出 depth、sumG 和倍增祖先表 up[u][j]；每次询问先用倍增表 $O(\log N)$ 求 LCA，再 $O(1)$ 套公式。这个预处理结构直接来自 rbook 的《倍增求 LCA》（模板 lca-binary-lifting）。

代码

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:58
 * update_at: 2026-08-12 22:58
 */
// 主解：倍增 LCA + 根路径 G 前缀计数（仿 rbook 模板 lca-binary-lifting 改造）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int LOG = 17; // 2^17 = 131072 > 1e5，足够覆盖最大深度

int n, m;
char color[MAXN];              // color[i] 为 'G' 或 'H'
vector<int> g[MAXN];           // 树的邻接表
int depth[MAXN];               // depth[i]：节点 i 到根 1 的深度（根深度为 1）
int up[MAXN][LOG + 1];         // up[u][j]：u 向上跳 2^j 步到达的祖先
int sumG[MAXN];                // sumG[i]：根到 i 的路径上 G 的数量（含 i 自己）

// 用 BFS 迭代预处理 depth、up 倍增表与根路径 G 前缀计数。
void build(int root) {
    queue<int> q;
    q.push(root);
    depth[root] = 1;
    sumG[root] = (color[root] == 'G');
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (v == up[u][0]) continue; // 跳过父亲
            up[v][0] = u;
            depth[v] = depth[u] + 1;
            sumG[v] = sumG[u] + (color[v] == 'G');
            for (int j = 1; j <= LOG; j++)
                up[v][j] = up[up[v][j - 1]][j - 1];
            q.push(v);
        }
    }
}

// 查询节点 u、v 的最近公共祖先。
int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    // 先把较深的节点向上跳到和较浅节点同一深度。
    int diff = depth[u] - depth[v];
    for (int j = 0; j <= LOG; j++)
        if (diff & (1 << j)) u = up[u][j];
    if (u == v) return u;
    // 再从大到小一起向上跳，最后停在 LCA 的下一层。
    for (int j = LOG; j >= 0; j--)
        if (up[u][j] != up[v][j]) {
            u = up[u][j];
            v = up[v][j];
        }
    return up[u][0];
}

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

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

    build(1);

    string ans;
    for (int i = 1; i <= m; i++) {
        int a, b;
        char want;
        cin >> a >> b >> want;

        int c = lca(a, b);
        // 路径 a->b 上 G 的数量（含端点，用前缀和容斥）。
        int cntG = sumG[a] + sumG[b] - 2 * sumG[c] + (color[c] == 'G');
        // 路径上的点数，H 的数量用总点数减 G 的数量补出。
        int len = depth[a] + depth[b] - 2 * depth[c] + 1;
        int cntH = len - cntG;

        if (want == 'G')
            ans.push_back(cntG > 0 ? '1' : '0');
        else
            ans.push_back(cntH > 0 ? '1' : '0');
    }
    cout << ans << '\n';

    return 0;
}

复杂度

时间：预处理 $O(N \log N)$ ，每次询问 $O(\log N)$ ，总 $O((N + M) \log N)$ 。
空间：倍增表 $O(N \log N)$ ，depth、sumG 与邻接表 $O(N)$ 。

总结

这道题是"树上路径点权计数"最标准的入门题：只维护一种颜色的根前缀，配合 LCA 容斥，把路径计数压到 $O(\log N)$ 。要点有两个——一是"只数 G，H 用路径长度补"，二是"路径 = 两条根路径 - 公共前缀 + LCA"。这两个技巧可以直接迁移到路径点权和、路径异或和等树上问题；以后学树上差分时，公式形式完全一样，只是把计数换成了差分值。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18朴素模拟（brute.cpp）
  每次询问沿路径 DFS 找路，逐点统计颜色      O(N) 每次询问
        |
        | 瓶颈：不复用信息，m 次询问 O(N*M) 太大
        v
关键观察（容斥）
  路径 a->b = 根到 a 的路径 + 根到 b 的路径
              - 公共前缀（根到 LCA）+ LCA 自己
  只数 G 一种颜色，H 用路径长度补
        |
        v
倍增 LCA + 根前缀计数（main.cpp）
  一次 BFS 预处理 depth / sumG / up 倍增表
  询问：O(log N) 求 LCA，O(1) 套容斥公式
  cntG > 0 或 cntH > 0 决定答案 1/0
        |
        v
复杂度 O((N + M) log N)，空间 O(N log N)

图中三条主线分别对应"暴力慢在哪里"“观察到什么性质”“正式解如何利用这个性质”。容斥公式把"统计任意路径上的颜色"变成"查两个根前缀和、减去一次公共前缀"，难度从逐点遍历降到两次表格查询；倍增 LCA 只负责回答公式里的 $\mathrm{lca}(a,b)$ 一项，两者拼装就是全部实现。

P5836 [USACO19DEC] Milk Visits S

题目描述

Farmer John 计划建造 $N$ 个农场，用 $N-1$ 条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为更赛牛或荷斯坦牛之一。

Farmer John 的 $M$ 个朋友经常前来拜访他。在朋友 $i$ 拜访之时，Farmer John 会与他的朋友沿着从农场 $A_i$ 到农场 $B_i$ 之间的唯一路径行走（可能有 $A_i = B_i$ ）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的有些朋友只喝更赛牛的牛奶，其余的只喝荷斯坦牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

请求出每个朋友在拜访过后是否会高兴。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$ 。

第二行包含一个长为 $N$ 的字符串。如果第 $i$ 个农场中的奶牛是更赛牛，则字符串中第 $i$ 个字符为 G，如果第 $i$ 个农场中的奶牛是荷斯坦牛则为 H。

以下 $N-1$ 行，每行包含两个不同的整数 $X$ 和 $Y$ （ $1 \leq X, Y \leq N$ ），表示农场 $X$ 与 $Y$ 之间有一条道路。

以下 $M$ 行，每行包含整数 $A_i$ ， $B_i$ ，以及一个字符 $C_i$ 。 $A_i$ 和 $B_i$ 表示朋友 $i$ 拜访时行走的路径的端点， $C_i$ 是 G 或 H 之一，表示第 $i$ 个朋友喜欢更赛牛的牛奶或是荷斯坦牛的牛奶。

输出格式

输出一个长为 $M$ 的二进制字符串。如果第 $i$ 个朋友会感到高兴，则字符串的第 $i$ 个字符为 1，否则为 0。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

在这里，从农场 1 到农场 4 的路径包括农场 1、2 和 4。所有这些农场里都是荷斯坦牛，所以第一个朋友会感到满意，而第二个朋友不会。

关于部分分：

测试点 $1$ 样例。

测试点 $2\sim 5$ 满足 $N\le 10^3$ ， $M\le 2\cdot 10^3$ 。

对于 $100\%$ 的数据， $1 \leq N \leq 10^5$ ， $1 \leq M \leq 10^5$ 。

供题：Spencer Compton

[USACO19DEC] Milk Visits S

目录

形式化题目

思路

代码

复杂度

总结

图示解析