3316. [USACO19 DEC Silver]Milk Visits

【题目描述】

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

Farmer John 的M 个朋友（1≤M≤10^5）经常前来拜访他。在朋友i拜访之时，Farmer John 会与他的朋友沿着从农场Ai到农场Bi之间的唯一路径行走（可能有Ai=Bi除此之外他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于

Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的有些朋友只喝更赛牛的牛奶，其余的只喝荷斯坦牛的牛奶。任何Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。请求出每个朋友在拜访过后是否会高兴。

【输入格式】

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

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

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

以下M 行，每行包含整数Ai，Bi，以及一个字符Ci。Ai 和Bi 表示朋友i 拜访时行走的路径的端点，Ci 是 'G' 或 'H' 之一,表示第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 到农场 4 的路径包括农场 1、2 和 4。所有这些农场里都是荷斯坦牛，所以第一个朋友会感到满意，而第二个朋友不会。

测试点性质：

测试点 2-5 满足N≤10^3,M≤2*10^3。