P9039 [PA 2021] Red-Black Tree

Are you familiar with the data structure called a red-black tree? In this problem, we will consider a tree whose nodes are colored red or black, but rest assured: if you have heard of the data structure mentioned above, it is best to forget it quickly. You are given a tree (that is, a connected undirected graph with no cycles), where each node is colored either red or black. You may choose two adjacent nodes $v$ and $u$ (connected by an edge), and recolor $v$ to have the same color as $u$. Your task is to determine whether, after a sequence of operations (**possibly performing no operations at all**), an initial coloring can be transformed into the given final coloring.

**This problem has multiple test cases.** The first line contains an integer $T$, the number of test cases. For each test case: The first line contains an integer $n$, the number of nodes in the tree. The second line contains $n$ characters, each being `0` or `1`. If the $i$-th character is `0`, then initially the $i$-th node is colored red. If the $i$-th character is `1`, then initially the $i$-th node is colored black. The third line contains $n$ characters, each being `0` or `1`. If the $i$-th character is `0`, then in the end the $i$-th node must be colored red. If the $i$-th character is `1`, then in the end the $i$-th node must be colored black. The next $n - 1$ lines each contain two integers $a_i, b_i$, describing an edge in the tree.

For each test case: Output one line with a string. If there exists a sequence of operations that transforms the coloring into the given final coloring, output `TAK`; otherwise output `NIE`.

Constraints: For $100\%$ of the testdata, $1 \leq T, n \leq 10^5$, $1 \leq \sum n \leq 10^6$, $1 \leq a_i, b_i \leq n$. Translated by ChatGPT 5