T2184F. Cherry Tree

dfs and similar, dp, graphs, trees, 1900, https://codeforces.com/problemset/problem/2184/F

You are given a rooted tree with 𝑛 vertices∗. The vertices of the tree are numbered with integers from 1 to 𝑛. The root of the tree is vertex number 1.

In each leaf† of the tree, there grows one cherry. You want to collect all the cherries, and to do this, you perform the following action several times:

You choose any vertex of the tree 𝑣 (including the root or a leaf) and "shake" it. After that, cherries fall from all the leaves that are descendants‡ of vertex 𝑣 (if vertex 𝑣 itself is a leaf, then a cherry falls from it). If cherries have already fallen from any leaf before, the tree will break, so such a situation must be avoided.

According to an ancient legend of the cherry orchard, the number of vertices you shake should be a multiple of three.

Is it possible to collect all the cherries in this way?

∗A tree with 𝑛 vertices is an undirected connected graph with 𝑛 vertices and 𝑛−1 edges. A rooted tree is a tree in which one of the vertices is special and is called the root.

†A leaf is a vertex that has no descendants.

‡The descendants of vertex 𝑣 are all vertices 𝑢≠𝑣 such that on the shortest path from the root to 𝑢, vertex 𝑣 is encountered.

Input

Each test consists of several test cases. The first line contains a single integer 𝑡 (1≤𝑡≤104) — the number of test cases. The following lines describe the test cases.

The first line of each test case contains a single integer 𝑛 (2≤𝑛≤2⋅105).

The next 𝑛−1 lines of each test case contain two integers 𝑢 and 𝑣 (1≤𝑢,𝑣≤𝑛,𝑢≠𝑣) — the vertices connected by the next edge of the tree.

It is guaranteed that the graph in each data set is a tree.

It is guaranteed that the sum of 𝑛 across all input data sets does not exceed 2⋅105.

Output

For each input data set, output "YES" on a separate line if it is possible to collect all the cherries. Otherwise, output "NO".

You can print each letter in any case (upper or lower). For example, "YeS", "no" and "yES" are all acceptable.

Example

input

output

YES
NO
YES

Note

In the first test case, you can shake vertices 2,3,4.

In the second test case, the only way to shake a number of vertices that is a multiple of three is to shake all the vertices. However, doing so would break the tree, so this is not allowed.

In the third test case, you can, for example, shake vertices 2,7,9.

【江昊中数学科学学院】思路：

dp 即可, dp[u][k] 表示以 u 为根的子树，能否用模 x 次操作覆盖所有叶子, 且 x mod 3 = k

代码

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<array<bool, 3>> dp(n, {false, false, false});

    auto dfs = [&](auto&& self, int u, int p) -> void {
        // 处理叶节点
        if (u != 0 && adj[u].size() == 1) {
            dp[u] = {false, true, false};
            return;
        }

        array<bool, 3> res = {true, false, false};
        for (int v : adj[u]) {
            if (v == p) continue;
            self(self, v, u);

            array<bool, 3> cur = {false, false, false};
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (dp[v][i] && res[j]) {
                        cur[(i + j) % 3] = true;
                    }
                }
            }
            res = cur;
        }
        dp[u] = res;
        dp[u][1] = true;
    };

    dfs(dfs, 0, -1);
    cout << ((dp[0][0]) ? "YES" : "NO") << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

【江昊中数学科学学院】CF2192D 感觉是一道很漂亮的贪心 + 树形 dp, 难点在于理清思路, 想清楚需要什么量和状态转移就不难. 2184F 也是树形 dp, 但感觉比 2192D 简单 (不懂为什么 2184F 有 1900, 而 2192D 只有 1800)

T2184F. Cherry Tree ​

T2184F. Cherry Tree