Milk Visits

题目描述

农夫约翰计划建造 $N$（$1 \leq N \leq 10^5$）个农场，并用 $N-1$ 条道路连接它们，形成一棵树（即任意两个农场互相可达，且不存在环）。每个农场里有一头奶牛，其品种要么是更赛（Guernsey），要么是荷斯坦（Holstein）。 农夫约翰有 $M$ 个朋友（$1 \leq M \leq 10^5$）经常来拜访他。在与第 $i$ 个朋友的拜访中，农夫约翰会和朋友沿着从农场 $A_i$ 到农场 $B_i$ 的唯一路径行走（也可能 $A_i = B_i$）。此外，他们可以品尝他们所走路径上任意一头奶牛的牛奶。由于农夫约翰的大多数朋友也是农民，他们对牛奶有很强的偏好。有些朋友只喝更赛牛奶，其余的只喝荷斯坦牛奶。只有当朋友在拜访过程中能够喝到自己偏好的牛奶类型时，他才会感到满意。 请判断每个朋友在拜访后是否会满意。

输入格式

第一行包含两个整数 $N$ 和 $M$。 第二行包含一个长度为 $N$ 的字符串。字符串的第 $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$ 个字符若为 '1'，表示第 $i$ 个朋友会满意；否则为 '0'。

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

10110

提示

SCORING: 测试点 2-5 满足 $N\le 10^3, M\le 2\cdot 10^3.$ 这里，从农场 1 到农场 4 的路径经过农场 1、2、4。它们全都是荷斯坦奶牛，因此第一个朋友会满意，而第二个不会。 题目来源：Spencer Compton

标签: USACO|2019|Silver

来源

USACO|2019|Silver