1495: Клуб любителів кави
Перегляд у форматі PDFКаллiсто очолює клуб любителiв кави i зараз очiкує на приїзд багатьох гостей. Вiн планує вiдвiдати ~N~ кавʼярень, якi зʼєднаннi ~N-1~ дорогою i ця сiтка дорiг утворює дерево. Кожна з цих кавʼярень має свiй фiрмовий кавовий напiй типу ~T_i~.
Очiкується приїзд ~M~ гостей. Пiд час приїзду гостя ~i~, Каллiсто разом з ним планує пройти унiкальним шляхом вiд кавʼярнi ~A_i~ до кавʼярнi ~B_i~ (можливий варiант ~A_i = B_i~ ). На своєму шляху вони будуть вживати кавовi напої. Кожен гiсть вiддає перевагу своїй улюбленi кавi i тому пʼє тiльки її. Зрозумiло, що гiсть буде задоволеним лише тодi, коли вiн скуштує свiй улюблений тип кави.
Ваша задача визначити чи буде задоволений кожен iз гостей.
Формат вхідних даних
Перший рядок мiстить цiлi числа ~N~ i ~M~ ~(1 \le N, M \le 10^5 )~.
Другий рядок мiстить ~N~ цiлих чисел ~T_1 , T_2 , ... , T_N~ . Тип фiрмового напою ~i~-ї кавʼярнi позначається через ~T_i~ ~(1 \le T_i \le N )~.
Далi iде ~N-1~ рядок, що мiстить цiлi числа ~X~ i ~Y~ ~(1 \le X, Y \le N )~, якi вказують наявнiсть дороги мiж кавʼярнями ~X~ i ~Y~ .
Наступнi ~M~ рядкiв мiстять цiлi числа ~A_i , B_i , C_i~. ~A_i~ i ~B_i~ вказують на початкову та кiнцеву кавʼярню пiд час вiзиту ~i~-го гостя, ~C_i~ ~(1 \le C_i \le N )~ - тип улюбленої кави цього гостя.
Всi числа роздiляються одним пропуском.
Формат вихідних даних
Виведiть двiйковий рядок довжиною ~M~. ~i~-й символ цього рядка має бути 1, якщо ~i~-й гiсть буде задоволений, в iншому випадку - 0.
Приклад вхідних даних
5 5
1 1 2 1 2
1 2
2 3
2 4
1 5
1 4 1
1 4 2
1 3 2
1 3 1
5 5 1
Приклад вихідних даних
10110
Приклад вхідних даних
6 4
1 2 3 3 3 3
1 2
2 3
3 4
2 5
5 6
4 6 1
4 6 2
4 6 3
4 6 4
Приклад вихідних даних
0110
Пояснення
В першому прикладi шлях iз 1 в 4 проходить через кавʼярнi 1, 2, 4. Всi вони пропонують каву типу 1. Перший гiсть буде задоволеним, а другий - нi...
Коментарі
на пайтон достатньо часу у і пам'яті?
підкорегував час та памʼять для java, python