[PA2021] Drzewo czerwono-czarne
题目描述
你熟悉红黑树这种数据结构吗?在本题我们将考虑一种节点颜色为红色或黑色的树,但请放心,如果你听说过刚才提到的数据结构的话,最好迅速忘掉它。
给定一棵树(即,一个无环的无向连通图),每个节点被涂成红或黑两种颜色之一。你可以选择被一条边相连的两个节点 $v$ 和 $u$,并把 $v$ 重新涂成和 $u$ 一样的颜色。
你的任务是确定经过一系列操作(**有可能不进行任何操作**)之后,一种最初的涂色情况能否变为最终给定的涂色情况。
输入输出格式
输入格式
**本题有多组测试数据。**
第一行,一个整数 $T$,表示数据组数。
对于每组数据:
第一行,一个整数 $n$,表示树的节点数;
第二行,$n$ 个字符,每个字符是 $0$ 或 $1$,如果第 $i$ 个字符是 $0$,则初始时第 $i$ 个节点被涂成红色。如果第 $i$ 个字符是 $1$,则初始时第 $i$ 个节点被涂成黑色;
第三行,$n$ 个字符,每个字符是 $0$ 或 $1$,如果第 $i$ 个字符是 $0$,则最后第 $i$ 个节点必须被涂成红色。如果第 $i$ 个字符是 $1$,则最后第 $i$ 个节点必须被涂成黑色;
接下来 $n - 1$ 行,其中第 $i$ 行有两个整数 $a_i, b_i$,表示树上的一条边;
输出格式
对于每组数据:
一行,一个字符串。如果存在一个操作序列能使涂色情况变为最终给定的情况,输出 `TAK`,否则输出 `NIE`。
输入输出样例
输入样例 #1
3
4
1011
1100
1 2
2 3
2 4
2
10
10
1 2
2
10
01
1 2
输出样例 #1
TAK
TAK
NIE
说明
对于 $100\%$ 的数据,$1 \leq T, n \leq 10^5$,$1 \leq \sum n \leq 10^6$,$1 \leq a_i, b_i \leq n$。