A336 | [USACO 2019 December Silver]Milk Visits

Farmer John's M friends (1≤M≤105) often come to visit him. During a visit with friend i, Farmer John will walk with his friend along the unique path of roads from farm Ai to farm Bi (it may be the case that Ai=Bi). Additionally, they can try some milk from any cow along the path they walk. Since most of Farmer John's friends are also farmers, they have very strong preferences regarding milk. Some of his friends will only drink Guernsey milk, while the remainder will only drink Holstein milk. Any of Farmer John's friends will only be happy if they can drink their preferred type of milk during their visit.

Please determine whether each friend will be happy after visiting.

SCORING:
Test cases 2-5 satisfy N≤103,M≤2⋅103.
INPUT FORMAT:
The first line contains the two integers N and M.
The second line contains a string of length N. The ith character of the string is 'G' if the cow in the ith farm is a Guernsey, or 'H' if the cow in the ith farm is a Holstein.

The next N−1 lines each contain two distinct integers X and Y (1≤X,Y≤N), indicating that there is a road between farms X and Y.

The next M lines contain integers Ai, Bi, and a character Ci. Ai and Bi represent the endpoints of the path walked during friend i's visit, while Ci is either G or H if the ith friend prefers Guernsey milk or Holstein milk.

OUTPUT FORMAT:
Print a binary string of length M. The ith character of the string should be '1' if the ith friend will be happy, or '0' otherwise.


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

Farmer John 的 $M$ 个朋友（1≤M≤$10^5$）经常前来拜访他。在朋友 $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≤X,Y≤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'$。