CF2184F

动态规划做法：

设 $dp_{u, i}$ 为在以 $u$ 为根的子树中选取 $i$ 个节点的情况下（模 3 意义下）是否可以摘掉子树中所有的樱桃。

如果 $u$ 没有被摇动，枚举它的子节点 $v$，设置状态 $dps_j$ 代表目前在子树中选了选了 $j$ 个节点能否摘掉所有的樱桃。初始： $dps_{0} = true, dps_{1}=false, dps_{2}=false$，转移：

if (dp[v][i] && dps[j]) dps[i + j] = true;

因为是这样转移的，所以初始什么都没选的情况下要设置为 true 否则无法转移。

枚举子节点的顺序将不影响最终结果。

最后把 $dps$ 赋值给 $dp_u$，这是不选 $u$ 的情况。

如果选 $u$ 的情况，那它的子树中将无法选择，设置 $dp_{u,1} = true$ 即可。

从根节点往下递归，如果是叶子节点，$dp_{u, 0}=false,dp_{u, 1}=true, dp_{u,2}=false$

最后答案是 $dp_{1, 0}$

转移注意新旧状态变换的问题。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<int>> adj;
vector<vector<bool>> dp;

void solve() {
  int n;
  cin >> n;
  adj.assign(n + 1, vector<int>());
  dp.assign(n + 1, vector<bool>(3, false));
  for (int i = 0, u, v; i < n - 1; i++) {
    cin >> u >> v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  function<void(int, int)> dfs = [&](int u, int pa) {
    vector<bool> cur(3, false);
    cur[0] = true;
    bool leaf = true;
    for (auto v : adj[u]) {
      if (v == pa) continue;
      leaf = false;
      dfs(v, u);
      vector<bool> nxt(3, false);
      for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) {
          if (cur[i] && dp[v][j]) {
            nxt[(i + j) % 3] = true;
          }
        }
      cur = nxt;
    }
    if (leaf) {
      dp[u][1] = true;
    } else {
      dp[u] = cur;
      dp[u][1] = true;
    }
  };
  dfs(1, -1);
  if (dp[1][0])
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}

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