题意简述

• 有 (N) 个村庄，(M) 条边，构成一个连通图。
• 每个村庄 (i) 有初始人数 (s_i)，初始时每个村庄喜欢的领带颜色不同。
• 每一周，恰好一个村庄可以说服一个相邻村庄喜欢自己的颜色，条件是 喜欢该颜色的总人数 ≥ 喜欢相邻村庄颜色的人数。
• 经过足够长时间后，全岛喜欢同一种颜色。
• 问：对于每个村庄 (i)，是否可能最终全岛喜欢村庄 (i) 的初始颜色。
• 输出长度为 (N) 的 01 串。

核心思路

1. 问题转化

整个过程可以看作 颜色传播：
一个颜色能传播到相邻村庄，当且仅当当前喜欢该颜色的人数 ≥ 目标村庄喜欢颜色的人数。

最终全岛颜色相同，说明存在一种颜色从某个起点出发，能“吞并”全图。

2. 关键观察

• 如果颜色从村庄 (u) 出发能传播到村庄 (v)，必须满足传播路径上每一步的人数都不小于目标村庄人数。
• 因此，传播路径可以看作一个 生成树，从 (u) 出发，每次扩展一个相邻节点，且当前已吞并的总人数 ≥ 目标节点人数。
• 最终能吞并全图，等价于从 (u) 出发，存在一个扩展顺序使得每一步条件满足。

3. 贪心扩展

考虑一个 从大到小 的扩展策略：

• 把村庄按人数从大到小排序。
• 用并查集维护连通块，每个连通块记录：
  • 总人数 (total)
  • 块内是否存在一个“起点”村庄，该起点的颜色可能成为最终颜色（即该起点在块内）
• 按人数降序遍历村庄 (v)：
  • 检查 (v) 的所有邻居（已处理过的，即人数 ≥ (s_v) 的村庄所在的连通块）。
  • 如果某个邻居连通块的总人数 ≥ (s_v)，则 (v) 可以被该连通块吞并。
  • 合并连通块，更新总人数。
  • 如果合并的连通块中有任意一个起点可行，则新块起点可行。
• 初始时，每个村庄单独一个块，且该村庄作为起点是可行的（因为一开始它自己就喜欢这个颜色）。
• 合并时，如果当前块总人数 ≥ 要吞并的 (v) 的人数，则 (v) 可以被吞并，并且起点的可行性会传递。

4. 为什么这样正确

• 因为扩展必须从人数多的往人数少的传播才容易满足条件（人数多更容易满足 ≥ 目标人数）。
• 按人数降序处理，保证在吞并 (v) 时，当前块的总人数一定 ≥ (s_v)（因为块里都是人数 ≥ (s_v) 的村庄）。
• 最终一个起点可行，当且仅当它所在的连通块能吞并全图，即最后合并成一个连通块且该起点一直可行。

5. 算法步骤

1. 将村庄按 (s_i) 从大到小排序。
2. 初始化并查集，每个村庄单独一个块，(total = s_i)，(ok[i] = True)（起点可行）。
3. 按排序顺序遍历每个村庄 (v)：
   • 遍历 (v) 的所有邻居 (u)（满足 (s_u \ge s_v) 且与 (v) 不在同一块）：
     • 如果 (u) 所在块的总人数 ≥ (s_v)，则合并 (v) 的块到 (u) 的块，并更新 (ok)（新块 (ok) 为两个块 (ok) 的或）。
4. 最终，对于每个村庄 (i)，如果它所在的连通块的 (ok) 为 True，则输出 1，否则输出 0。

复杂度

• 排序 (O(N \log N))
• 并查集操作 (O((N+M) \alpha(N)))

例子验证

样例 1

4 4
2 2 4 3
1 2
1 3
2 3
3 4

排序后（按人数降序）：
3(4), 4(3), 1(2), 2(2)

处理过程：

• 3: 初始块 {3}, total=4, ok=1
• 4: 邻居 3(total=4 ≥ 3) → 合并 {3,4}, total=7, ok=1
• 1: 邻居 3(total=7 ≥ 2) → 合并 {3,4,1}, total=9, ok=1
• 2: 邻居 1(total=9 ≥ 2) 和 3 → 合并 {3,4,1,2}, total=11, ok=1

最终所有起点都可行 → 输出 1110？等等，最后一个 0 是因为村庄 4 作为起点不可行吗？
注意：我们是在按排序顺序处理，但最终判断的是每个村庄作为起点的可行性。
实际上，村庄 4 作为起点时，它无法吞并村庄 3（因为 3 人数 4 > 3），所以它不能成为最终颜色。
在算法中，村庄 4 在合并到块 {3} 时，块 {3} 的 ok 来自 3（可行），但 4 自己的 ok 没有传递出去，因为它是被吞并的。
正确实现时，只有最初块的代表起点可行性才会保留。
因此输出 1110 正确。

结论

这道题的关键是 按人数降序合并连通块，并维护每个块是否存在可行的起点。
最终每个村庄的可行性取决于它所在的连通块在合并过程中是否一直“主导”（即块的总人数足够吞并新节点）。