Milk Visits

题目描述

农夫约翰计划建造 $N$（$1 \leq N \leq 10^5$）个农场，它们将由 $N-1$ 条道路连接，形成一棵树（即任意两个农场之间都可互相到达，并且没有环）。每个农场里有一头奶牛，其类型为 $1$ 到 $N$（含）之间的一个整数 $T_i$。 农夫约翰有 $M$ 个朋友（$1 \leq M \leq 10^5$）经常来拜访。第 $i$ 个朋友来访时，农夫约翰会和他沿着从农场 $A_i$ 到农场 $B_i$ 的唯一道路路径行走（可能出现 $A_i = B_i$）。此外，他们可以品尝沿途路径上任意奶牛的牛奶。 由于农夫约翰的大多数朋友也是农夫，他们对牛奶有很强的偏好。每位朋友只会喝某一种类型奶牛的牛奶。只有当他们在来访途中能够喝到自己偏好的牛奶类型时，才会感到开心。 请判断每位朋友来访后是否会开心。 计分说明： 测试点 2 是下面的第二个样例。 测试点 3 满足 $N\le 10^3, M\le 2\cdot 10^3$。 测试点 4-7 满足 $C_i\le 10$（$C_i$ 的定义见下文）。

输入格式

输入格式（文件 milkvisits.in）： 第一行包含两个整数 $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$）表示该朋友喜欢饮用的奶牛类型。

输出格式

输出格式（文件 milkvisits.out）： 输出一个长度为 $M$ 的二进制字符串。若第 $i$ 位朋友会开心，则字符串的第 $i$ 个字符为 '1'，否则为 '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

提示

在本样例中，从 1 到 4 的路径涉及农场 1、2 和 4。它们都包含类型为 1 的奶牛，因此第一位朋友会满意，而第二位不会。 题目致谢：Spencer Compton

标签: USACO|2019|Gold

来源

USACO|2019|Gold