首先将度数 \(-1\)。
设 \(f_i\) 为体积为 \(i\) 至多能用几个物品凑出来，\(g_i\) 为至少。
我们现在要证明一个东西：\(x \in [g_i, f_i]\)，\((i, x)\) 合法。
首先若 \((s, x)\) 合法，那么必须满足 \(s - x \in [-z, z - 2]\)，其中 \(z = \sum\limits_{i=1}^n [d_i = 0]\)。
因为 \(s - x = \sum\limits_{y \in S} (y - 1)\)，最小值就是把 \(< 1\) 的值加起来，最大值就是把 \(\ge 1\) 的值加起来。
然后 \([g_i, g_i + z]\) 一定能通过最少的方案后面加若干 \(0\) 凑出来，\([f_i - z, f_i]\) 同理。
那么只要满足 \(g_i + z + 1 \ge f_i - z\) 即 \(f_i - g_i \le 2z + 1\) 即可。
\((i, f_i)\) 和 \((i, g_i)\) 合法，那么 \(i - f_i \in [-z, z - 2], i - g_i \in [-z, z - 2]\)，所以它们的差 \(\in [0, 2z - 2]\)，得证。
和为 \(n\) 的数中至多有 \(O(\sqrt{n})\) 种不同的数。枚举这 \(n\) 个数，做多重背包即可。肯定不能直接朴素做，容易按照同余系分开考虑，单调队列优化。
code
// Problem: F - Tree Degree Subset Sum
// Contest: AtCoder - AtCoder Regular Contest 125
// URL: https://atcoder.jp/contests/arc125/tasks/arc125_f
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
int n, a[maxn], f[maxn], g[maxn], h[maxn], q[maxn], b[maxn];
void solve() {
scanf("%d", &n);
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
++a[u];
++a[v];
}
mems(f, -0x3f);
mems(g, 0x3f);
for (int i = 1; i <= n; ++i) {
--a[i];
++b[a[i]];
}
f[0] = g[0] = 0;
for (int i = 1; i <= n; ++i) {
if (!b[i]) {
continue;
}
for (int j = 0; j <= n; ++j) {
h[j] = f[j];
}
for (int j = 0; j < i; ++j) {
int hd = 1, tl = 0;
for (int k = j; k <= n; k += i) {
while (hd <= tl && q[hd] < k - i * b[i]) {
++hd;
}
if (hd <= tl) {
f[k] = max(f[k], h[q[hd]] + (k - q[hd]) / i);
}
while (hd <= tl && h[q[tl]] - q[tl] / i <= h[k] - k / i) {
--tl;
}
q[++tl] = k;
}
}
}
for (int i = 1; i <= n; ++i) {
if (!b[i]) {
continue;
}
for (int j = 0; j <= n; ++j) {
h[j] = g[j];
}
for (int j = 0; j < i; ++j) {
int hd = 1, tl = 0;
for (int k = j; k <= n; k += i) {
while (hd <= tl && q[hd] < k - i * b[i]) {
++hd;
}
if (hd <= tl) {
g[k] = min(g[k], h[q[hd]] + (k - q[hd]) / i);
}
while (hd <= tl && h[q[tl]] - q[tl] / i >= h[k] - k / i) {
--tl;
}
q[++tl] = k;
}
}
}
ll ans = 0;
for (int i = 0; i <= n; ++i) {
if (f[i] >= 0) {
ans += f[i] - g[i] + 1 + b[0];
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}