CF-1072-F. Cherry Tree（不要忘记 dp，特别是子问题相互重叠之时）

题目大意

给定一棵有 n 个顶点的有根树,根节点为 1。每个叶子节点上都有一个樱桃。

你需要通过"摇动"顶点来收集所有樱桃。摇动顶点 v 时,所有作为 v 后代的叶子节点上的樱桃都会掉落。每个叶子的樱桃只能掉落一次,否则树会损坏。

关键限制:摇动的顶点数量必须是 3 的倍数。

问题:是否可能在满足上述条件下收集所有樱桃?

输入格式:

• 第一行:测试用例数 t (1 ≤ t ≤ 10⁴)

• 每个测试用例:第一行为 n (2 ≤ n ≤ 2×10⁵),接下来 n-1 行描述树的边

**输出格式:**对每个测试用例输出 “YES” 或 “NO”

思路讲解

当你发现一个问题的子结构之间互相重叠覆盖，其中还涉及这个决策的时候，这个时候，你就要想，是不是 dp 了。

树上 dp，定义状态为 $dp_{u,i}$，指的是以 $u$ 为根的子树中，是否可以凑出来为这个 $i\ (0,1,2)$ 的这个 3 的余数。

接着问题就来到了如何转移？我们不妨定义，$to$ 为转移过来的子节点，四个你可以理解为 bitset 的东西，长度为 3，$bi$ 为目前的状态，若 $dp_{to,0}$ 为 true，那么 $bi1$ 就是这个 $bi$ 向前循环移动的结果，否则 $bi1$ 为全 0。同理，我们可以定义出 $bi0$，$bi2$。最终经过这个 $to$ 节点的转移后，$bi\gets bi0 \lor bi1 \lor bi2$。（当然，第一个 $to$ 节点转移过来的话，为了初值确定，$bi\gets dp_{to}$）

最后，令 $bi_1\gets \text{true}$（因为我们始终可以选择子树根节点，来解决这个问题），接着 $dp_u\gets bi$。

为什么要这么转移？我们会发现，就是说如果子树只有一个唯一的位移的话，是不是只是让这个状态进行一个位移？那么其实只有一个位移是没什么大用的，但是如果有两种位移？三种位移？这几种位移之间如何组合？那么答案就昭然若揭了。

AC代码

AC
https://codeforces.com/contest/2184/submission/357994744

源代码

/**
 * Problem: F. Cherry Tree
 * Contest: Codeforces Round 1072 (Div. 3)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2184/problem/F
 * Created: 2026-01-15 14:06:26
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<vector<ll>> g(N+2);
    for (int i=1;i<=N-1;++i) {
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<vector<int>> dp(N+2,vector<int>(3));
    auto dfs=[&](auto && self,ll u,ll p) -> void {
        vector<int> bi(3);
        // 循环左移
        auto left_move=[&](ll x) {
            vector<int> res(3);
            for (int i=0;i<3;++i) {
                res[(i+x)%3]=bi[i];
            }
            return res;
        };
        auto fun_or=[&](vector<int> a,vector<int> b) {
            for (int i=0;i<3;++i) {
                a[i]|=b[i];
            }
            return a;
        };
        int cnt =  0;

        for (auto v:g[u]) {
            if (v==p) continue;
            self(self,v,u);
            if (cnt ==  0) {
                bi=dp[v];
                cnt++;
                continue;
            }
            vector<int> bi1(3),bi2(3),bi0(3);
            if (dp[v][0]) {
                bi0=left_move(0);
            }
            if (dp[v][1]) {
                bi1=left_move(1);
            }
            if (dp[v][2]) {
                bi2=left_move(2);
            }
            bi=fun_or(bi0,fun_or(bi1,bi2));
        }
        bi[1]=1;
        dp[u]=bi;
    };
    dfs(dfs,1,0);

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2184/submission/357994744

*/

心路历程（WA，TLE，MLE……）