[PA 2021] Drzewo czerwono-czarne

Luogu
IDLGP9039
Time3000ms
Memory512MB
DifficultyP6
2021PA(波兰)
你熟悉红黑树这种数据结构吗?在本题我们将考虑一种节点颜色为红色或黑色的树,但请放心,如果你听说过刚才提到的数据结构的话,最好迅速忘掉它。 给定一棵树(即,一个无环的无向连通图),每个节点被涂成红或黑两种颜色之一。你可以选择被一条边相连的两个节点 $v$ 和 $u$,并把 $v$ 重新涂成和 $u$ 一样的颜色。 你的任务是确定经过一系列操作(**有可能不进行任何操作**)之后,一种最初的涂色情况能否变为最终给定的涂色情况。 ## Input **本题有多组测试数据。** 第一行,一个整数 $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$,表示树上的一条边; ## Output 对于每组数据: 一行,一个字符串。如果存在一个操作序列能使涂色情况变为最终给定的情况,输出 `TAK`,否则输出 `NIE`。 [samples] ## Note 对于 $100\%$ 的数据,$1 \leq T, n \leq 10^5$,$1 \leq \sum n \leq 10^6$,$1 \leq a_i, b_i \leq n$。
Samples
Input #1
3
4
1011
1100
1 2
2 3
2 4
2
10
10
1 2
2
10
01
1 2
Output #1
TAK
TAK
NIE
API Response (JSON)
{
  "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你的任务是确定经过一系列操作(**有可能不进行任何操作**)之后,一种最初的涂色情...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments