Молочные посещения (Золото)
Молочные посещения (Золото)
Фермер Джон планирует построить n ферм, которые будут соединены n - 1 дорогами, образуя дерево (то есть все фермы достижимы друг из друга, циклов нет). Каждая ферма содержит корову с целочисленным типом Ti
от 1 до n включительно.
m друзей фермера Джона часто навещают его. Во время визита друга i фермер Джон будет идти с ним по уникальному набору дорог от фермы Ai
до фермы Bi
(возможно, что Ai
= Bi
). Кроме того, они могут попробовать молока от любой коровы на своем пути. Поскольку большинство друзей фермера Джона также являются фермерами, у них очень сильные предпочтения в отношении молока. Каждый из его друзей будет пить молоко только от определенной породы коров. Любой из друзей фермера Джона будет счастлив только в том случае, если сможет выпить предпочитаемый сорт молока во время своего визита.
Определите, будет ли счастлив каждый друг в результате визита.
Входные данные
Первая строка содержит два целых числа n (1 ≤ n ≤ 105
) и m (1 ≤ m ≤ 105
). Во второй строке записано n целых чисел T1
, T2
,..., Tn
. Тип коровы на i -ой ферме обозначается Ti
.
Следующие n - 1 строк содержат по два различных целых числа x и y (1 ≤ x, y ≤ n), что указывает на то, что между фермами x и y существует дорога.
В следующих m строках записаны целые числа Ai
, Bi
и Ci
. Ai
и Bi
представляют собой конечные точки пути, пройденного во время посещения друга i, в то время как Ci
(1 ≤ Ci
≤ n) указывает на сорт коровы, молоко которой любит пить друг.
Выходные данные
Выведите двоичную строку длины m. i - ый символ строки должен быть '1', если i - ый друг будет счастлив, и '0' в противном случае.
Пример
В этом примере путь от 1 до 4 включает фермы 1, 2 и 4. Все они содержат коров типа 1, поэтому первый друг будет доволен, а второй - нет.
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