题目描述

\\n\\n

\\n\\t农夫约翰计划建造$ N $个农场，用$ N−1 $条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。\\n

\\n

\\n\\t每个农场有一头奶牛，品种为更赛牛或荷斯坦牛之一。\\n

\\n

\\n\\t约翰的$ M $个朋友经常前来拜访他。\\n

\\n

\\n\\t在朋友$ i $拜访之时，约翰会与他的朋友沿着从农场$ A_i $到农场$ B_i $之间的唯一路径行走（可能有$ A_i=B_i $）。\\n

\\n

\\n\\t除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。\\n

\\n

\\n\\t由于约翰的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。\\n

\\n

\\n\\t他的有些朋友只喝更赛牛的牛奶，其余的只喝荷斯坦牛的牛奶。\\n

\\n

\\n\\t任何约翰的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。\\n

\\n

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

\\n

输入格式

\\n\\n

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

\\n

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

\\n

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

\\n

\\n\\t以下$ M $行，每行包含整数$ A_i,B_i$，以及一个字符$ C_i $。\\n

\\n

\\n\\t$ A_i $和$ B_i $表示朋友 i拜访时行走的路径的端点，$ C_i$是 ‘G’ 或 ‘H’ 之一，表示第$ i $个朋友喜欢更赛牛的牛奶或是荷斯坦牛的牛奶。\\n

\\n

\\n\\n

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

\\n

\\n

Status	Submit By	Time	Memory	Language	Code	Submit At
AC	jike1994	1202ms	6.3 MiB	C++14(O2)	806 Bytes	2025-3-21 14:10:55
AC	沈鼎皓	2351ms	28.5 MiB	C++14(O2)	2.7 KiB	2025-4-7 6:09:44