题目描述

给定一棵有 $n$ 个结点的有根树 $^{\text{∗}}$，树的结点编号为 $1$ 到 $n$。树的根结点是 $1$ 号结点。

每一片叶子 $^{\text{†}}$ 上都结有一颗樱桃。你想采集所有的樱桃，为此你需要多次执行如下操作：

你可以选择树上的任意一个结点 $v$（可以是根或叶子），并“摇晃”它。之后，所有以 $v$ 为祖先的叶子上的樱桃都会掉下来（如果 $v$ 自身是叶子，则自身的樱桃会掉下）。若某片叶子的樱桃被摇落过多次，树就会损坏，因此要避免这种情况。

据传樱桃园的古老传说，你摇晃的结点数必须是 $3$ 的倍数。

你能否用这种方式采集所有的樱桃？

$^{\text{∗}}$ 一棵有 $n$ 个结点的树是一个含 $n$ 个结点、$n-1$ 条边的无向连通图。有根树是指定一个特殊结点为根的树。

$^{\text{†}}$ 叶子是没有子结点的结点。

$^{\text{‡}}$ 结点 $v$ 的后代是所有路径从根到 $u \neq v$，且路径上必经 $v$ 的所有结点 $u$。

输入格式

每组测试数据包含若干个测试用例。第一行为单个整数 $t$ $(1 \le t \le 10^4)$，表示测试用例的组数。以下为各组测试用例的数据。

每组数据的第一行为一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$）。

随后 $n-1$ 行，每行两个整数 $u$ 与 $v$（$1 \leq u, v \leq n, u \neq v$），表示一条树上的边，连接结点 $u$ 和 $v$。

保证每组数据的图都是一棵树。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，若可以采集所有樱桃，则在单独一行输出 “YES”；否则输出 “NO”。

可以以任意大小写输出答案（例如 “YeS”、“no”、“yES” 都是可接受的）。

样例

3
4
1 2
1 3
1 4
3
1 2
1 3
9
1 2
3 1
2 4
5 2
5 6
3 7
8 3
8 9

YES
NO
YES

样例说明

在第一个测试用例中，你可以摇晃结点 $2, 3, 4$。

在第二个测试用例中，唯一能摇晃的结点数量是 $3$ 的倍数时，只能摇晃所有结点，但这样会让树损坏，所以不允许。

在第三个测试用例中，你可以例如摇晃结点 $2, 7, 9$。

由 ChatGPT 5 翻译

来源

Codeforces 2184F，英文题名 Cherry Tree。