[USACO19DEC] Milk Visits G
题目描述
Farmer John 计划建造 $N$ 个农场,用 $N-1$ 条道路连接,构成一棵树(也就是说,所有农场之间都互相可以到达,并且没有环)。每个农场有一头奶牛,品种为 $1$ 到 $N$ 之间的一个整数 $T_i$。
Farmer John 的 $M$ 个朋友经常前来拜访他。在朋友 $i$ 拜访之时,Farmer John 会与他的朋友沿着从农场 $A_i$ 到农场 $B_i$ 之间的唯一路径行走(可能有 $A_i = B_i$)。除此之外,他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主,他们对牛奶有着极强的偏好。他的每个朋友都只喝某种特定品种的奶牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。
请求出每个朋友在拜访过后是否会高兴。
输入输出格式
输入格式
输入的第一行包含两个整数 $N$ 和 $M$。
第二行包含 $N$ 个空格分隔的整数 $T_1,T_2,\ldots, T_N$。第 $i$ 个农场内的奶牛的品种用 $T_i$ 表示。
以下 $N-1$ 行,每行包含两个不同的整数 $X$ 和 $Y$($1 \leq X, Y \leq N$),表示农场 $X$ 与 $Y$ 之间有一条边。
以下 $M$ 行,每行包含整数 $A_i$,$B_i$,以及$C_i$。$A_i$ 和 $B_i$ 表示朋友 $i$ 拜访时行走的路径的端点,$C_i$($1\le C_i\le N$)表示这个朋友喜欢的牛奶的奶牛品种。
输出格式
输出一个长为 $M$ 的二进制字符串。如果第 $i$ 个朋友会感到高兴,则字符串的第 $i$ 个字符为 `1`,否则为 `0`。
输入输出样例
输入样例 #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
输出样例 #1
10110
输入样例 #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
输出样例 #2
0110
说明
测试点性质:
测试点 $2$ 为以下第二个样例。
测试点 $3$ 满足 $N\le 10^3$,$M\le 2\cdot 10^3$。
测试点 $4\sim 7$ 满足 $C_i\le 10$。
对于 $100\%$ 的数据,$1 \leq N \leq 10^5$,$1 \leq M \leq 10^5$。
供题:Spencer Compton