Молочні відвідування (Срібло)#10289
Фермер Джон планує побудувати ферм, які будуть з'єднані n - 1 дорогами, утворюючи дерево (тобто всі ферми досяжні одна з одної, циклів немає). На кожній фермі є корова породи Гернсі або Голштин.
друзів фермера Джона часто навідують його. Під час візиту друга фермер Джон буде йти з ним по унікальному набору доріг від ферми A_i до ферми B_i (можливо A_i = B_i). Крім того, вони можуть спробувати молока від будь-якої корови на своєму шляху. Оскільки більшість друзів фермера Джона також є фермерами, у них дуже сильні уподобання щодо молока. Деякі з його друзів будуть пити тільки молоко Гернсі, а решта будуть пити тільки молоко Голштин. Будь-який з друзів фермера Джона буде щасливий лише в тому випадку, якщо зможе випити улюблений сорт молока під час свого візиту.
Визначте, чи буде щасливий кожен друг в результаті візиту.
Перший рядок містить два цілих числа (1 \leq n \leq 10^5) і (1 \leq m \leq 10^5). Другий рядок містить рядок довжини . -ий символ рядка дорівнює 'G', якщо корова на -й фермі Гернсі, і 'H', якщо корова на -й фермі Голштинська.
Наступні n - 1 рядків містять по два різних цілих числа і (1 \leq x, y \leq n), що вказує на те, що між фермами і є дорога.
У наступних рядках записані цілі числа A_i, B_i і символ C_i. A_i і B_i представляють собою кінцеві точки шляху, пройденого під час відвідування друга , тоді як C_i означає G або H якщо -ий друг віддає перевагу молоку Гернсі або молоку Голштинської породи.
Виведіть двійковий рядок довжини . -ий символ рядка повинен бути '1', якщо -ий друг буде щасливий, і '0' в іншому випадку.
Приклад 1
Шлях від ферми до ферми включає ферми , і . Всі вони містять Голштинів, тому перший друг буде задоволений, а другий ні.