{"problem":{"name":"[PA 2021] Drzewo czerwono-czarne","description":{"content":"你熟悉红黑树这种数据结构吗？在本题我们将考虑一种节点颜色为红色或黑色的树，但请放心，如果你听说过刚才提到的数据结构的话，最好迅速忘掉它。 给定一棵树（即，一个无环的无向连通图），每个节点被涂成红或黑两种颜色之一。你可以选择被一条边相连的两个节点 $v$ 和 $u$，并把 $v$ 重新涂成和 $u$ 一样的颜色。 你的任务是确定经过一系列操作（**有可能不进行任何操作**）之后，一种最初的涂色情","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9039"},"statements":[{"statement_type":"Markdown","content":"你熟悉红黑树这种数据结构吗？在本题我们将考虑一种节点颜色为红色或黑色的树，但请放心，如果你听说过刚才提到的数据结构的话，最好迅速忘掉它。\n\n给定一棵树（即，一个无环的无向连通图），每个节点被涂成红或黑两种颜色之一。你可以选择被一条边相连的两个节点 $v$ 和 $u$，并把 $v$ 重新涂成和 $u$ 一样的颜色。\n\n你的任务是确定经过一系列操作（**有可能不进行任何操作**）之后，一种最初的涂色情况能否变为最终给定的涂色情况。\n\n## Input\n\n**本题有多组测试数据。**\n\n第一行，一个整数 $T$，表示数据组数。\n\n对于每组数据：\n\n第一行，一个整数 $n$，表示树的节点数；\n\n第二行，$n$ 个字符，每个字符是 $0$ 或 $1$，如果第 $i$ 个字符是 $0$，则初始时第 $i$ 个节点被涂成红色。如果第 $i$ 个字符是 $1$，则初始时第 $i$ 个节点被涂成黑色；\n\n第三行，$n$ 个字符，每个字符是 $0$ 或 $1$，如果第 $i$ 个字符是 $0$，则最后第 $i$ 个节点必须被涂成红色。如果第 $i$ 个字符是 $1$，则最后第 $i$ 个节点必须被涂成黑色；\n\n接下来 $n - 1$ 行，其中第 $i$ 行有两个整数 $a_i, b_i$，表示树上的一条边；\n\n## Output\n\n对于每组数据：\n\n一行，一个字符串。如果存在一个操作序列能使涂色情况变为最终给定的情况，输出 `TAK`，否则输出 `NIE`。\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 的数据，$1 \\leq T, n \\leq 10^5$，$1 \\leq \\sum n \\leq 10^6$，$1 \\leq a_i, b_i \\leq n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9039","tags":["2021","PA（波兰）"],"sample_group":[["3\n4\n1011\n1100\n1 2\n2 3\n2 4\n2\n10\n10\n1 2\n2\n10\n01\n1 2","TAK\nTAK\nNIE"]],"created_at":"2026-03-03 11:09:25"}}