2199 - Milk Visits

题目描述

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

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

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

输入

输入的第一行包含两个整数 NM

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

以下 N-1 行,每行包含两个不同的整数 XY1 \leq X, Y \leq N),表示农场 XY 之间有一条道路。

以下 M 行,每行包含整数 A_iB_i,以及一个字符 C_iA_iB_i 表示朋友 i 拜访时行走的路径的端点,C_iGH 之一,表示第 i 个朋友喜欢更赛牛的牛奶或是荷斯坦牛的牛奶。

输出

输出一个长为 M 的二进制字符串。如果第 i 个朋友会感到高兴,则字符串的第 i 个字符为 1,否则为 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
说明

样例 1 解释

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

数据范围

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

对于 100\% 的数据,1 \leq N \leq 10^51 \leq M \leq 10^5

来源

标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题