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\le X,Y\le 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

5 5
HHGHG
1 2
2 3
2 4
1 5
1 4 H
1 4 G
1 3 G
1 3 H
5 5 H

输出 #1

10110

说明/提示

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

关于部分分：

测试点 $1$ 样例。

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

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

供题：Spencer Compton

solution

• 1 以 1 为根节点。统计每个节点 u 到根节点的 H 和 G 奶牛的个数 H[u], G[u]
• 2 找到 x,y 的最小公共祖先 z, 则 H 奶牛数量为 H[x] + H[y] - 2H[z] + a[z],G 也相同计算

代码

#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "set"
#include "queue"
#include "algorithm"
#include "bitset"
#include "cstring"

using namespace std;

/*
 * 题目大意：n (<=1e5) 个农场组成一颗树，每个农场养 H 和 G 奶牛种的一种. m(<=2e3)个人，每人喜欢
 * H 和 G 奶牛中的一种，并且选择两个点从x，y，问他在路上能否碰到自己喜欢的牛
 * 思路:
 * 1 以 1 为根节点。统计每个节点 u 到根节点的 H 和 G 奶牛的个数 H[u], G[u]
 * 2 找到 x,y 的最小公共祖先 z, 则 H 奶牛数量为 H[x] + H[y] - 2H[z] + a[z],G 也相同计算
 */

const int N = 1e5 + 1;

int n, m, H[N], G[N], d[N], f[N][20];
char a[N];
vector<int> e[N];

void dfs(int u, int p) {
    f[u][0] = p;
    for (int i = 1; i < 20; i++) f[u][i] = f[f[u][i - 1]][i - 1];
    H[u] = H[p] + (a[u] == 'H');
    G[u] = G[p] + (a[u] == 'G');
    d[u] = d[p] + 1;
    for (int v: e[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
}

int lca(int x, int y) {
    if (x == y) return x;
    if (d[x] < d[y]) swap(x, y);
    for (int i = 19; d[x] != d[y]; i--)
        if (d[f[x][i]] >= d[y]) x = f[x][i];
    if (x == y) return x;

    for (int i = 19; i >= 0; i--)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}


int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }

    dfs(1, 0);

    for (int i = 1; i <= m; i++) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        int z = lca(x, y);

        if (c == 'H') {
            int t = H[x] + H[y] - 2 * H[z] + (a[z] == 'H');
            cout << (t ? 1 : 0);
        } else {
            int t = G[x] + G[y] - 2 * G[z] + (a[z] == 'G');
            cout << (t ? 1 : 0);
        }
    }
    return 0;
}

结果