#PU970. USACO 2019 December Contest, Gold — Problem 2. Milk Visits

    ID: 1274 传统题 文件IO:milkvisits 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec19来源:usaco.orgscoring:equal_test_cases树上算法深搜

USACO 2019 December Contest, Gold — Problem 2. Milk Visits

USACO 2019 December Contest, Gold — Problem 2. Milk Visits

题目描述

Farmer John is planning to build NN (1≤N≤1051 \leq N \leq 10^5) farms that will be connected by N−1N-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 TiT_i between 11 and NN inclusive. Farmer John's MM friends (1≤M≤1051 \leq M \leq 10^5) often come to visit him. During a visit with friend ii, Farmer John will walk with his friend along the unique path of roads from farm AiA_i to farm BiB_i (it may be the case that Ai=BiA_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.

输入格式

The first line contains two integer NN and MM. The second line contains NN space-separated integers T1,T2,…,TN.T_1,T_2,\ldots, T_N. The type of the cow in the ii-th farm is denoted by Ti.T_i. The next N−1N-1 lines each contain two distinct integers XX and YY (1≤X,Y≤N1 \leq X, Y \leq N), indicating that there is an edge between farms XX and YY. The next MM lines contain integers AiA_i, BiB_i, and CiC_i. AiA_i and BiB_i represent the endpoints of the path walked during friend ii's visit, while CiC_i (1≤Ci≤N1\le C_i\le N) indicates the type of cow whose milk the friend enjoys drinking.

输出格式

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

数据范围

Test case 2 is the second example case below. Test case 3 satisfies N≤103,M≤2⋅103N\le 10^3, M\le 2\cdot 10^3. Test cases 4-7 satisfy Ci≤10C_i\le 10 (CiC_i defined below).

样例

样例 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
Problem credits: Spencer Compton