树上的 DP 以及 和树有关的 DP
A - Svjetlo
https://www.luogu.com.cn/problem/P7163
很容易想到一种状态设计，即令 \(f_{x,0/1/2}\) 分别表示有 \(0/1/2\) 个端点在子树内部的情况；然后就开始思考，如何满足对于开关状态的要求？
还是想少了。如果再加一维，从『状态为开或关』思考就会轻松很多，令 \(f_{x,0/1/2,0/1}\) 表示有 \(0/1/2\) 个端点再子树外部，且子树内操作完后 \(x\) 为关 / 开的最少步数。然后分类讨论转移方式即可。
一个比较方便的讨论方式是，先确定某种情况下，访问 \(u\) 与 \(v\) 的次数，然后就可以得到它们原本的状态。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, rt = -1;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
char t;
std::cin >> t;
a[i] = t - '0';
if (!a[i])
rt = i;
}
if (rt == -1) {
std::cout << 0 << '\n';
return 0;
}
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<int> tag(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
tag[x] = a[x];
for (auto i : g[x])
if (i != fa)
DFS(i, x), tag[x] &= tag[i];
return;
};
DFS(rt, -1);
std::vector<std::vector<std::vector<int> > > f(n + 1, std::vector<std::vector<int> > (3, std::vector<int> (2, 0x3f3f3f3f)));
DFS = [&](int x, int fa) {
f[x][0][a[x]] = 0;
for (auto i : g[x])
if (i != fa && !tag[i]) {
DFS(i, x);
auto g = f[x];
f[x][0][0] = std::min(g[0][0] + f[i][0][1] + 4, g[0][1] + f[i][0][0] + 2);
f[x][0][1] = std::min(g[0][1] + f[i][0][1] + 4, g[0][0] + f[i][0][0] + 2);
f[x][1][0] = std::min({ g[1][0] + f[i][0][1] + 4, g[1][1] + f[i][0][0] + 2, g[0][0] + f[i][1][0] + 3, g[0][1] + f[i][1][1] + 1 });
f[x][1][1] = std::min({ g[1][1] + f[i][0][1] + 4, g[1][0] + f[i][0][0] + 2, g[0][1] + f[i][1][0] + 3, g[0][0] + f[i][1][1] + 1 });
f[x][2][0] = std::min({ g[2][0] + f[i][0][1] + 4, g[2][1] + f[i][0][0] + 2, g[1][0] + f[i][1][1], g[1][1] + f[i][1][0] + 2, g[0][0] + f[i][2][1] + 4, g[0][1] + f[i][2][0] + 2 });
f[x][2][1] = std::min({ g[2][1] + f[i][0][1] + 4, g[2][0] + f[i][0][0] + 2, g[1][1] + f[i][1][1], g[1][0] + f[i][1][0] + 2, g[0][1] + f[i][2][1] + 4, g[0][0] + f[i][2][0] + 2 });
}
f[x][1][0] = std::min(f[x][1][0], f[x][0][1] + 1);
f[x][1][1] = std::min(f[x][1][1], f[x][0][0] + 1);
f[x][2][0] = std::min(f[x][2][0], f[x][1][0]);
f[x][2][1] = std::min(f[x][2][1], f[x][1][1]);
// for (int i = 0; i < 3; ++i)
// for (int j = 0; j < 2; ++j)
// printf("f[%d][%d][%d] = %d\n", x, i, j, f[x][i][j]);
return;
};
DFS(rt, -1);
std::cout << f[rt][2][1] << '\n';
return 0;
}B - One to One
https://atcoder.jp/contests/arc140/tasks/arc140_d
观察原图上连通块，发现要么是没有未确定边的基环树，要么是有恰好一条未确定边的树。缩点，任意为未确定边赋值，考察最后得到的连通块，发现要么是以『基环树点』为根的树，要么是不包含『基环树点』的（内向）基环树。
这里要用到贡献的思想。考虑将全局划分为若干个部分，保证每部分的单步价值是可确定的。将第一步，即对树和基环树的讨论拆开，对于树，其数量确定；对于基环树，发现环的数量即为基环树的数量，进一步将所有步中的『环』这一类分开，统计成环的方案数就可以得到基环树的贡献。具体地，令 \(f_{i,j}\) 为在前 \(i\) 个点中选择 \(j\) 个成一个环的方案数，则有：
\[ f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times siz_i \]
最后计算每个环的贡献即可。注意还要算上环内部的排列（注意循环位移）。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<int> a(n + 1), tag(n + 1), s(n + 1, 1), fa(n + 1), siz(n + 1);
std::iota(fa.begin() + 1, fa.end(), 1);
std::function<int(int)> find = [&](int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
};
auto merge = [&](int x, int y) {
x = find(x), y = find(y);
if (x != y) {
tag[y] += tag[x];
s[y] += s[x];
fa[x] = y;
}
return;
};
for (int i = 1; i <= n; ++i) {
std::cin >> a[i], fa[i] = i;
if (a[i] == -1)
tag[i] = 1;
else
merge(i, a[i]);
}
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; ++i) {
cnt1 += (fa[i] == i && !tag[i]);
if (fa[i] == i && tag[i])
siz[++cnt2] = s[i];
}
auto qkp = [&](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
auto res(cnt1 * qkp(n, cnt2) % mod);
std::vector<std::vector<long long> > f(cnt2 + 1, std::vector<long long> (cnt2 + 1));
f[0][0] = 1ll;
for (int i = 1; i <= cnt2; ++i) {
// printf("i = %d, siz = %d: \n", i, siz[i]);
for (int j = 0; j <= i; ++j) {
f[i][j] = f[i - 1][j];
if (j != 0)
(f[i][j] += f[i - 1][j - 1] * siz[i]) %= mod;
// printf(" f[%d][%d] = %lld\n", i, j, f[i][j]);
}
}
for (int i = 1; i <= cnt2; ++i) {
static auto fac(1ll);
(res += f[cnt2][i] * fac % mod * qkp(n, cnt2 - i) % mod) %= mod;
(fac *= i) %= mod;
}
std::cout << res << '\n';
return 0;
}C - Diameter Cuts
https://codeforces.com/problemset/problem/1499/F
令 \(f_{x,i}\) 表示 \(x\) 上的最长链长为 \(i\) 的方案数，就可以用一个类似背包的过程求答案了。发现这个背包满足可以被优化的形式，故能在 \(O(nk)\) 内解决问题。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, k;
std::cin >> n >> k, ++k;
if (k == 0) {
std::cout << 1 << '\n';
return 0;
}
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<int> h(n + 1);
std::vector<std::vector<long long> > f(n + 1, std::vector<long long> (k + 1));
std::function<void(int, int)> DFS = [&](int x, int fa) {
f[x][1] = 1ll, h[x] = 1;
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
std::vector<long long> g(k + 1);
g.swap(f[x]);
for (int j = std::min(h[x], k); j; --j)
for (int l = std::min(h[i], k - j); ~l; --l)
(f[x][std::max(j, l + 1)] += g[j] * f[i][l] % mod) %= mod;
h[x] = std::max(h[x], h[i] + 1);
}
for (int i = 1; i <= h[x] && i <= k; ++i)
(f[x][0] += f[x][i]) %= mod;
// for (int i = 0; i <= h[x] && i <= k; ++i)
// printf("f[%d][%d] = %lld\n", x, i, f[x][i]);
return;
};
DFS(1, -1);
auto res(0ll);
for (int i = 1; i <= k; ++i)
(res += f[1][i]) %= mod;
std::cout << res << '\n';
return 0;
}D - Leaf Partition
https://codeforces.com/problemset/problem/1146/F
假设已经完成分组，欲判定这种方式是否合法，容易想到对每一组叶子建立虚树，则该分组方式合法，当且仅当没有一个点被多个虚树占用。也即，我们需要在总的虚树上选出一些点，让它们可以覆盖所有叶子。
虚树上 DP，容易发现当且仅当存在 \(\ge 2\) 个儿子想要分进同一个虚树时，\(i\) 会被选到。故令 \(f_{i, 0/1/2}\) 表示当前有 \(0/1/\ge 2\) 个儿子想要选择 \(i\) 时的方案数，DP 即可。
在实现的过程中就会发现根本不需要求虚树，原树上 DP 就可以了。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<int> fa(n + 1);
std::vector<std::vector<int> > g(n + 1);
for (int i = 2; i <= n; ++i)
std::cin >> fa[i], g[fa[i]].push_back(i);
std::vector<std::array<long long, 3> > f(n + 1);
std::function<void(int)> DFS = [&](int x) {
if (g[x].empty())
f[x][2] = 1ll;
else
f[x][0] = 1ll;
for (auto i : g[x]) {
DFS(i);
auto F0 = (f[i][0] + f[i][2]) % mod, F1 = (f[i][1] + f[i][2]) % mod;
f[x][2] = (f[x][2] * F0 % mod + f[x][2] * F1 % mod + f[x][1] * F1 % mod) % mod;
f[x][1] = (f[x][1] * F0 % mod + f[x][0] * F1 % mod) % mod;
(f[x][0] *= F0) %= mod;
}
// printf("%d: %lld / %lld / %lld\n", x, f[x][0], f[x][1], f[x][2]);
return;
};
DFS(1);
std::cout << (f[1][0] + f[1][2]) % mod << '\n';
return 0;
}E - Uniformly Branched Trees
https://codeforces.com/problemset/problem/724/F
感觉是很常见的套路，但是我不会 😱
在手玩样例的时候可以感性认知到，每个树会被每种点作为根的情况统计一次。且如果固定以某种（化学环境）的点为根，可以通过按 siz 从小到大排列唯一求解出该树。
发现以重心为根（即钦定根为重心）可以带来很多优美的性质。因为 siz 是好确定的，且是儿子的排序依据，所以选重心便于统计，同时满足每种树最多被统计两次（当且仅当有两个重心）。
发现这就变成了多重集的组合数，设 \(f_{i,j,k}\) 表示已经花费 \(i\) 个点组成一个子树，子树的根节点当前已经确认了 \(j\) 个儿子，最靠右的一个 siz \(\le k\) 的方案数。得到 \(f_{i,j,k}=\sum_{x=0} f_{i-x\cdot k,j-x,k-1}\cdot \binom{f_{k,d-1,k}+x-1}{x}\)（相当于将 \(x\) 个无标号的位置 / 球分配给 \(f_{k,d-1,k}\) 个有标号的选项 / 盒子，插板即可）。
若 \(n\) 为奇数，则可直接输出 \(f_{n,d,\lfloor\frac n2\rfloor}\)；若 \(n\) 为偶数，则可能存在两个重心，即需要统计拥有两个重心，且以两个重心分别为根时长相不同的树种类。这种情况下显然存在一条边，左右两边 siz 相同且长相不同。故数量为 \(\binom{f_{\lfloor \frac n2\rfloor, d-1,\lfloor \frac n2\rfloor}}{2}\)，容斥掉即可。
需要特判 \(n\le2\) 的情况。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, d, mod;
std::cin >> n >> d >> mod;
if (n <= 2) {
std::cout << 1 << '\n';
return 0;
}
using arr = std::vector<long long>;
using brr = std::vector<arr>;
using crr = std::vector<brr>;
auto qkp = [&](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
arr inv(d + 1);
inv[0] = inv[1] = 1ll;
auto fac = 1ll;
for (int i = 2; i <= d; ++i) {
(fac *= i) %= mod;
inv[i] = qkp(fac, mod - 2);
}
auto C = [&](long long n, int m) {
if (m == 0)
return 1ll;
if (m > n)
return 0ll;
auto res(1ll);
for (auto i = 0; i < m; ++i)
(res *= n - i) %= mod;
return res * inv[m] % mod;
};
crr f(n + 1, brr(d + 1, arr(n / 2 + 1)));
f[1][0][0] = 1ll;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= d && 1 + j <= i; ++j) {
for (int x = 0; x <= j && x <= i; ++x)
f[i][j][1] += f[i - x][j - x][0];
f[i][j][1] %= mod;
for (int k = 2; k <= n / 2; ++k) {
// bool flag = (i == 10 && j == 3 && k == 3);
for (int x = 0; x <= j && x * k <= i; ++x) {
f[i][j][k] += f[i - x * k][j - x][k - 1] * C(f[k][d - 1][k - 1] + x - 1, x);
// if (flag)
// printf("x = %d, f[%d][%d][%d](%lld) * C(%lld, %d)(%lld)\n", x, i - x * k, j - x, k - 1, f[i - x * k][j - x][k - 1], f[k][d - 1][k - 1] + x - 1, x, C(f[k][d - 1][k - 1] + x - 1, x));
}
f[i][j][k] %= mod;
}
}
// for (int i = 1; i <= n; ++i)
// for (int j = 0; j <= d && j <= i - 1; ++j, puts(""))
// for (int k = 0; k <= n / 2; ++k) {
// printf("f[%d][%d][%d] = %lld\n", i, j, k, f[i][j][k]);
// }
if (n & 1)
std::cout << f[n][d][n / 2] << '\n';
else {
auto res(f[n][d][n / 2]);
res = (res + mod - C(f[n / 2][d - 1][n / 2 - 1], 2)) % mod;
std::cout << res << '\n';
}
return 0;
}A - Dominant Indices
https://codeforces.com/problemset/problem/1009/F
长剖板子；难点在于可能要复习一下长剖怎么写。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<int> h(n + 1), son(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
h[x] = 1;
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
h[x] = std::max(h[x], h[i] + 1);
if (h[i] > h[son[x]])
son[x] = i;
}
return;
};
DFS(1, -1);
std::vector<int> _f(2 * n + 1), res(n + 1);
auto pos(_f.begin());
std::vector<decltype(pos)> f(n + 1);
DFS = [&](int x, int fa) {
++f[x][0];
if (!son[x]) {
res[x] = 0;
return;
}
f[son[x]] = std::next(f[x]);
DFS(son[x], x);
int mx = -std::max(std::make_pair(f[x][res[son[x]] + 1], -(res[son[x]] + 1)), std::make_pair(1, 0)).second;
for (auto i : g[x])
if (i != fa && i != son[x]) {
f[i] = pos, pos = std::next(pos, h[i] + 1);
DFS(i, x);
for (int j = 0; j <= h[i]; ++j) {
f[x][j + 1] += f[i][j];
if (j + 1 != mx && std::make_pair(f[x][j + 1], -(j + 1)) > std::make_pair(f[x][mx], -mx))
mx = j + 1;
}
}
// printf("%d: ", x);
// for (int i = 0; i <= h[x]; ++i)
// printf("%d ", f[x][i]);
// puts("");
res[x] = mx;
return;
};
f[1] = pos, pos = std::next(pos, h[1]);
DFS(1, -1);
for (int i = 1; i <= n; ++i)
std::cout << res[i] << '\n';
return 0;
}B - 树上异或
https://www.luogu.com.cn/problem/P9745
和 Svjetlo 很像，把连通块的异或和放到状态里，拆位后令 \(f_{i,j,0/1}\) 表示点 \(i\) 所在的连通块在第 \(j\) 位异或和为 \(0/1\) 的权值（不计 \(i\) 所在连通块），转移即可。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<long long> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::vector<std::vector<int> > g(n + 1);
for (int i = 2, x; i <= n; ++i) {
std::cin >> x;
g[x].push_back(i), g[i].push_back(x);
}
std::vector<long long> dp(n + 1);
std::vector<std::array<std::array<long long, 2>, 60> > f(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
for (int i = 0; i < 60; ++i)
f[x][i][(a[x] >> i) & 1] = 1ll;
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
for (int j = 0; j < 60; ++j) {
auto f1 = f[x][j];
f[x][j][0] = (f1[0] * dp[i] % mod + f1[0] * f[i][j][0] % mod + f1[1] * f[i][j][1] % mod) % mod;
f[x][j][1] = (f1[1] * dp[i] % mod + f1[0] * f[i][j][1] % mod + f1[1] * f[i][j][0] % mod) % mod;
}
}
for (int i = 0; i < 60; ++i)
dp[x] += (1ll << i) % mod * f[x][i][1] % mod;
dp[x] %= mod;
return;
};
DFS(1, -1);
std::cout << dp[1] << '\n';
return 0;
}C - 一个网的路
https://www.luogu.com.cn/problem/P8595
首先需要意识到，树和链的边数是一样的，炸掉了多少条边，在之后就会花多少代价补回来。故炸一个点的代价为度数 +1。对于一个点 \(u\)，分为四种可能性：
- 被炸了，单独作为一个连通块。
- 没被炸，儿子全部被炸了。
- 没被炸，有 1 个儿子没被炸。
- 没被炸，有 2 个儿子没被炸。
分别用 \(f_{u,0/1/2/3}\) 代表上面四种可能性，转移即可。
贺了个 fread，擦边跑过了。这个不是 \(O(n)\) 的吗？
#include <bits/stdc++.h>
const int LEN = (1 << 20);
#ifdef ONLINE_JUDGE
int nec(void) {
static char buf[LEN], *p = buf, *e = buf;
if (p == e) {
e = buf + fread(buf, 1, LEN, stdin);
if (e == buf) return EOF;
p = buf;
}
return *p++;
}
#else
#define nec getchar
#endif
bool read(int &x) {
x = 0;
bool f = 0;
char ch = nec();
while (ch < '0' || ch > '9') {
if (ch == EOF) return 0;
if (ch == '-') f = 1;
ch = nec();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = nec();
}
if (f) x = -x;
return 1;
}
void print(int x) {
if (x < 0)
putchar('-'), x = -x;
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
return;
}
void print(int x, char ch) {
print(x), putchar(ch);
return;
}
int main() {
int n, m;
read(n), read(m);
int res = (n - 1) - m;
std::vector<std::vector<int> > g(n + 1);
for (int x, y; m--; ) {
read(x), read(y);
g[x].push_back(y), g[y].push_back(x);
}
std::vector<int> tag(n + 1);
std::vector<std::array<int, 4> > f(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
tag[x] = 1;
f[x][0] = (fa != -1) + 1;
f[x][2] = f[x][3] = 0x3f3f3f3f;
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
f[x][3] = std::min(f[x][3] + f[i][0], f[x][2] + std::min(f[i][1], f[i][2]));
f[x][2] = std::min(f[x][2] + f[i][0], f[x][1] + std::min(f[i][1], f[i][2]));
f[x][1] += f[i][0];
f[x][0] += std::min({ f[i][0] - 1, f[i][1], f[i][2], f[i][3] }) + 1;
}
return;
};
for (int i = 1; i <= n; ++i)
if (!tag[i]) {
DFS(i, -1);
res += *std::min_element(f[i].begin(), f[i].end());
}
print(res, '\n');
return 0;
}D - 随机树
https://www.luogu.com.cn/problem/P3830
对于第一问，令 \(f_x\) 表示共有 \(x\) 个叶子时的期望深度，两个新叶子的期望深度为 \(f_{x-1}+1\)，delta 为 \(f_{x-1}+2\)，故有 \(f_x=\dfrac {(x-1)f_{x-1}+f_{x-1}+2}x\)，递推即可。
对于第二问，令 \(f_{x,k}\) 表示有 \(x\) 个叶子，深度 \(\ge k\) 的概率（一种理解是从整数概率公式的角度出发）。则考虑枚举左、右叶子数，对于左侧叶子数为 \(i\) 的情况，为了去重，只选择深度为 \(k-1\) 的叶子展开。只考虑某种组合的出现概率，为 \(f_{i,k-1}+f_{x-i,k-1}-f_{i,k-1}\cdot f_{x-i,k-1}\)。数归可以证明，对于任意 \(i\)，深度为 \(k-1\) 的叶子被选中的概率均为 \(\dfrac 1{x-1}\)。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int q, n;
std::cin >> q >> n;
std::cout << std::fixed << std::setprecision(6);
if (q == 1) {
std::vector<double> f(n + 1);
for (int i = 2; i <= n; ++i)
f[i] = (f[i - 1] * (i - 1) + f[i - 1] + 2.) / i;
std::cout << f[n] << '\n';
}
else {
std::vector<std::vector<double> > f(n + 1, std::vector<double> (n + 1));
for (int i = 1; i <= n; ++i) {
f[i][0] = 1.;
for (int j = 1; j < i; ++j) {
auto s(0.);
for (int k = 1; k < i; ++k)
s += f[k][j - 1] + f[i - k][j - 1] - f[k][j - 1] * f[i - k][j - 1];
f[i][j] = s / (i - 1);
}
}
auto res(0.);
for (int i = 1; i < n; ++i)
res += f[n][i];
std::cout << res << '\n';
}
return 0;
}E - Complete Compress
https://atcoder.jp/contests/agc034/tasks/agc034_e
对于链，发现可以枚举最后聚集的点，答案与配对方式无关，check 是否能配对即可。
如果不是链，则相比链，还可以选择同一子树中不存在祖孙关系的两个点，将它们都向 LCA 移一步。
故而，可以在链的做法上打一个补丁，观察到先『内部消化』，再在子树间配对一定不劣，且答案仍然和配对方式无关。故令 \(f_x\) 表示点 \(x\) 内最多消掉多少对，就可以 check 了。
#include <bits/stdc++.h>
const long long inf = 1e18;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("line_02.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
char t;
std::cin >> t;
a[i] = t - '0';
}
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
auto res(inf);
for (int i = 1; i <= n; ++i) {
std::vector<int> s(n + 1);
std::vector<long long> f(n + 1), cnt(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
s[x] = a[x];
int son = 0;
auto sum(0ll);
for (auto i : g[x])
if (i != fa) {
DFS(i, x), s[x] += s[i];
sum += cnt[i];
if (cnt[i] > cnt[son])
son = i;
}
if (son) {
if (cnt[son] * 2 <= sum)
f[x] = sum / 2;
else
f[x] = sum - cnt[son] + std::min(f[son], (cnt[son] - (sum - cnt[son])) / 2);
}
cnt[x] = sum;
if (x != i)
cnt[x] += s[x];
return;
};
DFS(i, -1);
if (cnt[i] % 2 == 0 && f[i] == cnt[i] / 2)
res = std::min(res, cnt[i] / 2);
}
if (res == inf)
std::cout << -1 << '\n';
else
std::cout << res << '\n';
return 0;
}