题目
[ARC157E] XXYX Binary Tree
一个很显然的暴力，\(f_{u,a,b,c}\) 表示在在 \(u\) 的子树中，是否有 \(a\) 个 XX，\(b\) 个 XY，\(c\) 个 YX。
这个状态 \(O(n^4)\) 的，考虑优化，可以先省去一个 \(c\)，变成 \(f_{u,a,b}\)，因为 \(a+b+c\) 的总和是知道的。
然后优化不了了……
只能重新设计，发现都没有用上二叉树的条件，显然要找一点性质的。
可以发现 \(Y\) 的个数好像可以确定，如果 \(Y\) 为非根节点，那么 \(Y\) 的数量有 \(B\) 个，否则就有 \(B+1\) 个，因为一个除了根节点的 \(Y\) 肯定可以贡献一个 XY。
还可以发现非叶子的 \(Y\) 可以贡献两个 YX。
然后就可以刻画 XY 和 YX 的数量了，这里分根节点是否为 \(Y\) 两种情况。
如果根不为 \(Y\)，那么一共有 \(B\) 个 \(Y\)，记叶子节点为 \(Y\) 的个数为 \(sum\)，那么 YX 的数量就是 \(2(B-sum)\)，所以 \(sum\) 满足 \(sum=B-\frac{C}{2}\)。
如果根为 \(Y\)，那么一共有 \(B+1\) 个 \(Y\)，记叶子节点为 \(Y\) 的个数为 \(sum\)，那么 YX 的数量就是 \(2(B+1-sum)\)，所以 \(sum\) 满足 \(sum=B+1-\frac{C}{2}\)。
所以设 \(f_{u,i,0/1}\) 表示 \(u\) 的子树中有 \(i\) 个叶子为 \(Y\) 且 \(u\) 是否是 \(Y\) 时最多有多少个非叶子的 \(Y\)。
这里可以 \(O(n^2)\) 树上背包转移。
代码
#include <bits/stdc++.h>void Freopen() {freopen("", "r", stdin);freopen("", "w", stdout);
}using namespace std;
const int N = 1e4 + 10, M = 2e5 + 10, inf = 1e9, mod = 998244353;int n, A, B, C;
int f[N][N][2], siz[N];vector< int> G[N];void dfs( int u) {siz[u] = 0;if (! G[u].size()) {siz[u] = 1;f[u][0][0] = 0, f[u][1][1] = 0;return ;}f[u][0][0] = 0, f[u][0][1] = 1;for ( auto v : G[u]) {dfs(v);// 这里注意，必须要倒叙枚举，这样才能保证不会用到已经被转移过的信息for ( int i = siz[u]; i >= 0; i --)for ( int j = siz[v]; j >= 0; j --) {f[u][i + j][0] = max(f[u][i + j][0], f[u][i][0] + max(f[v][j][0], f[v][j][1]));f[u][i + j][1] = max(f[u][i + j][1], f[u][i][1] + f[v][j][0]);}siz[u] += siz[v];}
}void solve() {cin >> n >> A >> B >> C;for ( int i = 1; i <= n; i ++) {G[i].clear();for ( int j = 0; j <= B + 1; j ++)f[i][j][0] = f[i][j][1] = -inf;}for ( int i = 2, fa; i <= n; i ++)cin >> fa, G[fa].push_back(i);if (C & 1) return cout << "No\n", void();dfs(1);if (B - C / 2 >= 0 && f[1][B - C / 2][0] >= C / 2) {cout << "Yes\n";return ;}if (B + 1 - C / 2 >= 0 && f[1][B + 1 - C / 2][1] >= C / 2) {cout << "Yes\n";return ;}cout << "No\n";
}signed main() {ios :: sync_with_stdio(false);cin.tie(0), cout.tie(0);int t; cin >> t;while (t --) solve();return 0;
}