Description

\n

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

\n

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

\n

Input Format

\n

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

\n

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

\n

\n\t以下 N-1 行，每行包含两个不同的整数 X 和 Y（1≤X,Y≤N），表示农场 X 与 Y 之间有一条道路。\n以下 M 行，每行包含整数 Ai\n ，Bi\n ，以及一个字符 Ci\n 。Ai\n 和 Bi\n 表示朋友 i 拜访时行走的路径的端点，Ci\n 是 G 或 H 之一，表示第 i 个朋友喜欢更赛牛的牛奶或是荷斯坦牛的牛奶。\n

\n

\n\t1≤N≤10⁵ ，1≤M≤10⁵。\n

\n

Output Format

\n输出一个长为 M 的二进制字符串。如果第 i 个朋友会感到高兴，则字符串的第 i 个字符为 1，否则为 0。\n

统计

递交统计

【基础】Milk Visits

信息

登录