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