题目大意
给定一棵有 n 个顶点的有根树,根节点为 1。每个叶子节点上都有一个樱桃。
你需要通过"摇动"顶点来收集所有樱桃。摇动顶点 v 时,所有作为 v 后代的叶子节点上的樱桃都会掉落。每个叶子的樱桃只能掉落一次,否则树会损坏。
关键限制:摇动的顶点数量必须是 3 的倍数。
问题:是否可能在满足上述条件下收集所有樱桃?
输入格式:
**输出格式:**对每个测试用例输出 “YES” 或 “NO”
思路讲解
当你发现一个问题的子结构之间互相重叠覆盖，其中还涉及这个决策的时候，这个时候，你就要想，是不是 dp 了。
树上 dp，定义状态为 dpu,i，指的是以 u 为根的子树中，是否可以凑出来为这个 i (0,1,2) 的这个 3 的余数。
接着问题就来到了如何转移？我们不妨定义，to 为转移过来的子节点，四个你可以理解为 bitset 的东西，长度为 3，bi 为目前的状态，若 dpto,0 为 true，那么 bi1 就是这个 bi 向前循环移动的结果，否则 bi1 为全 0。同理，我们可以定义出 bi0，bi2。最终经过这个 to 节点的转移后，bi←bi0∨bi1∨bi2。（当然，第一个 to 节点转移过来的话，为了初值确定，bi←dpto）
最后，令 bi1←true（因为我们始终可以选择子树根节点，来解决这个问题），接着 dpu←bi。
为什么要这么转移？我们会发现，就是说如果子树只有一个唯一的位移的话，是不是只是让这个状态进行一个位移？那么其实只有一个位移是没什么大用的，但是如果有两种位移？三种位移？这几种位移之间如何组合？那么答案就昭然若揭了。
AC代码
AC
https://codeforces.com/contest/2184/submission/357994744
源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
#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 CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353;
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;
}
|
心路历程（WA，TLE，MLE……）
