P5836 [USACO19DEC] Milk Visits S

题目描述

Farmer John 计划建造 $N$ 个农场,用 $N-1$ 条道路连接,构成一棵树(也就是说,所有农场之间都互相可以到达,并且没有环)。每个农场有一头奶牛,品种为更赛牛或荷斯坦牛之一。 Farmer John 的 $M$ 个朋友经常前来拜访他。在朋友 $i$ 拜访之时,Farmer John 会与他的朋友沿着从农场 $A_i$ 到农场 $B_i$ 之间的唯一路径行走(可能有 $A_i = B_i$)。除此之外,他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主,他们对牛奶有着极强的偏好。他的有些朋友只喝更赛牛的牛奶,其余的只喝荷斯坦牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。 请求出每个朋友在拜访过后是否会高兴。

输入格式

输出格式

说明/提示

在这里,从农场 1 到农场 4 的路径包括农场 1、2 和 4。所有这些农场里都是荷斯坦牛,所以第一个朋友会感到满意,而第二个朋友不会。 关于部分分: 测试点 $1$ 样例。 测试点 $2\sim 5$ 满足 $N\le 10^3$,$M\le 2\cdot 10^3$。 对于 $100\%$ 的数据,$1 \leq N \leq 10^5$,$1 \leq M \leq 10^5$。 供题:Spencer Compton