Description

Farmer John plans to build $N$ farms and connect them with $N-1$ roads to form a tree (that is, every pair of farms is reachable, and there are no cycles). Each farm has one cow, with breed $T_i$, an integer between $1$ and $N$.

Farmer John has $M$ friends who often come to visit him. When friend $i$ visits, Farmer John and this friend will walk along the unique path from farm $A_i$ to farm $B_i$ (it is possible that $A_i = B_i$). In addition, they can taste the milk of any cow on the path they travel. Since most of Farmer John’s friends are also farmers, they have strong preferences for milk. Each friend only drinks milk from one specific breed of cow. A friend will be happy only if, during their visit, they can drink milk of their preferred breed.

Please determine whether each friend will be happy after the visit.

Input Format

The first line contains two integers $N$ and $M$.

The second line contains $N$ space-separated integers $T_1,T_2,\ldots, T_N$. The cow breed on farm $i$ is given by $T_i$.

The next $N-1$ lines each contain two distinct integers $X$ and $Y$ ($1 \leq X, Y \leq N$), indicating there is an edge between farms $X$ and $Y$.

The next $M$ lines each contain integers $A_i$, $B_i$, and $C_i$. $A_i$ and $B_i$ are the endpoints of the path friend $i$ walks during the visit, and $C_i$ ($1 \le C_i \le N$) is the cow breed whose milk this friend likes.

Output Format

Output a binary string of length $M$. If friend $i$ will be happy, the $i$-th character of the string is 1, otherwise it is 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

Hint

Test point properties.

Test point $2$ is the second sample below.

Test point $3$ satisfies $N\le 10^3$, $M\le 2\cdot 10^3$.

Test points $4\sim 7$ satisfy $C_i\le 10$.

For $100\%$ of the testdata, $1 \leq N \leq 10^5$, $1 \leq M \leq 10^5$.

Problem author: Spencer Compton.

Translated by ChatGPT 5