페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4133

Milk Visits 2초 512MB

문제

Farmer John is planning to build N (1 \leq N \leq 10^5) farms that will be connected by N-1 roads, forming a tree (i.e., all farms are reachable from each-other, and there are no cycles). Each farm contains a cow with an integer type T_i between 1 and N inclusive.

Farmer John's M friends (1 \leq M \leq 10^5) often come to visit him. During a visit with friend i, Farmer John will walk with his friend along the unique path of roads from farm A_i to farm B_i (it may be the case that A_i = B_i). Additionally, they can try some milk from any cow along the path they walk. Since most of Farmer John's friends are also farmers, they have very strong preferences regarding milk. Each of his friends will only drink milk from a certain type of cow. Any of Farmer John's friends will only be happy if they can drink their preferred type of milk during their visit.

Please determine whether each friend will be happy after visiting.

SCORING:

  • Test case 2 is the second example case below.

  • Test case 3 satisfies N\le 10^3, M\le 2\cdot 10^3.

  • Test cases 4-7 satisfy C_i\le 10 (C_i defined below).

Problem credits: Spencer Compton


입력

The first line contains two integer N and M.

The second line contains N space-separated integers T_1,T_2,\ldots, T_N. The type of the cow in the i-th farm is denoted by T_i.

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

The next M lines contain integers A_i, B_i, and C_i. A_i and B_i represent the endpoints of the path walked during friend i's visit, while C_i (1\le C_i\le N) indicates the type of cow whose milk the friend enjoys drinking.


출력

Print a binary string of length M. The ith character of the string should be '1' if the ith friend will be happy, or '0' otherwise.


예제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

In this example, the path from 1 and 4 involves farms 1, 2, and 4. All of these contain cows of type 1, so the first friend will be satisfied while the second one will not.


예제2

입력
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

출처

USACO 2019 December Gold

역링크 공식 문제집만