题意回顾

给定一棵树，每个节点有初始颜色（红/黑）和目标颜色（红/黑）。
操作：选择一条边 $(u,v)$，将 $u$ 的颜色变成 $v$ 的颜色。
判断能否通过若干操作使所有节点达到目标颜色。

数据范围：$t \leq 10^5$，$\sum n \leq 10^6$。

---

关键观察

1. 操作性质分析

操作相当于颜色沿着边传播。
如果节点 $u$ 和 $v$ 相邻，那么 $u$ 的颜色可以变成 $v$ 的颜色。

这意味着颜色可以从一个节点传播到整个连通分量。

2. 必要条件

不变性 1：如果目标状态全是同一种颜色，那么只要初始状态至少有一个节点是这种颜色，就可以实现。

不变性 2：操作不会改变颜色的连通性。更精确地说，如果两个节点在目标状态中颜色不同，那么它们在初始状态中必须已经属于不同的"颜色连通分量"。

---

算法核心

1. 构建颜色连通分量

考虑目标颜色的连通性：
在目标状态中，将颜色相同的相邻节点合并到同一个连通分量中。

对于每个这样的连通分量 $C$：

• 如果 $C$ 中所有节点在初始状态都是目标颜色：可以直接实现
• 如果 $C$ 中至少有一个节点在初始状态是目标颜色：可以通过传播实现
• 如果 $C$ 中所有节点在初始状态都是另一种颜色：无法实现

2. 关键结论

对于每个目标颜色的连通分量 $C$：

• 必须存在至少一个节点 $v \in C$，使得初始颜色 $init[v] = 目标颜色$

因为颜色只能从已有的节点传播，不能凭空产生新颜色。

---

算法步骤

1. 读入初始颜色数组 init 和目标颜色数组 target
2. 如果 init == target，直接输出 TAK
3. 构建目标颜色的连通分量：
   • 遍历所有边 $(u,v)$
   • 如果 target[u] == target[v]，将 $u$ 和 $v$ 合并到同一连通分量
4. 对每个连通分量检查：
   • 是否存在至少一个节点 $v$ 满足 init[v] == target[v]
5. 如果所有连通分量都满足条件，输出 TAK，否则输出 NIE

---

正确性证明

充分性

如果每个目标连通分量都有至少一个正确颜色的起点，那么：

• 从这些起点开始，颜色可以沿着边传播到整个分量
• 由于树是连通的，传播过程可以覆盖所有节点

必要性

如果某个目标连通分量没有任何正确颜色的起点：

• 该分量中的所有节点初始都是错误颜色
• 颜色只能从外部传播进来，但外部节点的目标颜色不同
• 无法使该分量变成目标颜色

---

实现细节

并查集优化

使用并查集来合并目标颜色相同的相邻节点：

检查条件

对每个连通分量的代表元，检查该分量中是否存在至少一个节点满足： init[v] == target[v]

可以用数组标记每个连通分量是否满足条件。

---

复杂度分析

• 并查集操作：$O(n \alpha(n))$
• 检查条件：$O(n)$
• 总复杂度：$O(n \alpha(n))$，可处理 $\sum n \leq 10^6$

---

解法

标准解法是：

对于每个目标颜色的连通分量，检查是否存在一条边连接该分量和另一个不同颜色的分量，且这条边连接的两个节点在初始状态中颜色不同。

但更简单的实现是：
从所有初始颜色与目标颜色相同的节点开始 BFS/DFS，标记所有可达节点。如果所有节点都被标记，则输出 TAK，否则 NIE。

---

最终算法

1. 如果 init == target，输出 TAK
2. 构建图
3. 从所有满足 init[v] == target[v] 的节点开始 BFS
4. 在 BFS 中，只能沿着边走到满足 target[u] == target[v] 的节点
5. 如果 BFS 访问了所有节点，输出 TAK，否则 NIE

---

总结

本题的核心在于理解颜色传播的连通性：

1. 颜色只能沿着目标颜色相同的边传播
2. 传播必须从初始正确的节点开始
3. 通过 BFS 检查是否所有节点都能从正确起点到达

时间复杂度 $O(n)$，可处理大规模数据。