感觉挺不错的一道题，不过课上 pb 好像没有讲。
显然树的具体形态对题目影响不大，那么我们知道 \(\sum\limits_{i=1}^nd_i=2n-2\) 即可扔掉树的条件。即：
给定 \(n\) 个 \(d_i\)，和为 \(2n-2\)，求 \((x,y)\) 满足 \(0\le x\le n\) 且 \(\exists S\subseteq \{1,2,\cdots n\},|S|=x,\sum\limits_{i\in S}d_i=y\) 的数量。
我们考虑如何解决这个问题。首先可以将所有 \(d_i\) 减去 \(1\)，那么 \(\sum\limits_{i=1}^nd_i=n-2\)。然后我们考虑证明，对于任意的 \(y\)，设 \(m(y)\) 和 \(M(y)\) 为最小和最大的 \(x\) 使得 \((x,y)\) 合法，那么有 \(\forall i\in [m(y),M(y)]\)，\((i,y)\) 合法：
- 设 \(x(S)=|S|,y(S)=\sum\limits_{i\in S}d_i\)。
- 我们设 \(d_i=0\) 的 \(i\) 的个数为 \(z\)，由于 \(m(y)\) 的方案中没有选 \(d_i=0\) ，\(M(y)\) 的方案中一定选了 \(z\) 个 \(d_i=0\)，所以只需要证明 \(M(y)-m(y)\le 2z+1\) 即可通过调整 \(0\) 的个数构造出 \(x\in [m(y),M(y)]\)。
- 由于对于每个集合 \(S\in \{1,2,\cdots n\}\)，\(-z\le y(S)-x(S)\le z-2\)（左边全取 \(0\)，右边全取非 \(0\)），所以对于任意的 \(y\)，\(-z\le y-M(y)\le y-m(y)\le z-2\)，解不等式即可得到 \(M(y)-m(y)\le 2z-2\)。
考虑得到了 \(\forall i\in [m(y),M(y)]\)，\((i,y)\) 合法这个结论，如何求出方案数。由于 \(y\le n-2\)，考虑处理出对于每个 \(y\)，\(M(y)\) 和 \(m(y)\) 的值，然后对 \(M(y)-m(y)+1\) 求和就是答案。
注意到 \(d\) 的总和为 \(n-2\)，显然 \(d_i\) 中非 \(0\) 的互不相同的数至多只有 \(O(\sqrt n)\) 个，不难想到用单调队列优化多重背包。具体地，以 \(M(y)\) 为例，设 \(c_i=\sum\limits_{j=1}^n[d_j=i]\)，\(f_{i,j}\) 表示考虑了 \(1\) 到 \(i\) 中的所有 \(d_k=i\)，当前 \(y(S)\) 为 \(j\) 的方案数。那么：
\[f_{i,j}\gets \max\limits_{k=0}^{c_i}(f_{i-1,j-ki}+k) \]套路地将 \(j\) 拆成 \(xi+y\)，且 \(0\le y<i\)，设 \(g_{y,x}=f_{i,xi+y}\)，\(g'_{y,x}=f_{i-1,xi+y}\)：
\[\begin{aligned}g_{y,x}&=\max\limits_{k=0}^{c_i}(g'_{y,x-k}+k)\\&=\max\limits_{k=0}^{c_i}(g'_{y,x-k}-(x-k))+x\end{aligned} \]这就是经典的单调队列优化的形式了。考虑外层枚举 \(y\le i\)，内层 \(x\le \left\lfloor\dfrac{n}{i}\right\rfloor\)，物品数量为 \(O(\sqrt n)\)，总复杂度是 \(n\sqrt n\) 的。
最后统计答案需要将 \(d_i=0\) 的贡献算上。
// 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 int long long
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define ins insert
#define era erase
typedef tuple<int, int, int> tu3;
typedef pair<int, int> pi;
inline int rd() {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void wr(int x) {
if (x < 0) x = ~(x - 1), putchar('-');
if (x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
}
using namespace vbzIO;
const int N = 2e5 + 200;
const int inf = 0x3f3f3f3f;
int n, ct, hd, tl, q[N], d[N], c[N], L[N], R[N], f[N], g[N];
int w(int x) { return g[x] - x; }
signed main() {
n = rd();
for (int i = 1, u, v; i <= n - 1; i++)
u = rd(), v = rd(), d[u]++, d[v]++;
for (int i = 1; i <= n; i++)
d[i]--, ct += (!d[i]), c[d[i]]++;
memset(R, -inf, sizeof(R));
memset(L, inf, sizeof(L));
L[0] = R[0] = 0;
for (int i = 1; i <= n; i++) {
if (!c[i]) continue;
for (int y = 0; y < i; y++) {
for (int x = 0; x <= n / i; x++)
g[x] = R[x * i + y], f[x] = -inf;
hd = 1, tl = 0;
for (int x = 0; x <= n / i; x++) {
while (hd <= tl && q[hd] < x - c[i]) hd++;
while (hd <= tl && w(q[tl]) <= w(x)) tl--;
q[++tl] = x;
f[x] = w(q[hd]) + x;
R[x * i + y] = max(R[x * i + y], f[x]);
}
}
}
for (int i = 1; i <= n; i++) {
if (!c[i]) continue;
for (int y = 0; y < i; y++) {
for (int x = 0; x <= n / i; x++)
g[x] = L[x * i + y], f[x] = inf;
hd = 1, tl = 0;
for (int x = 0; x <= n / i; x++) {
while (hd <= tl && q[hd] < x - c[i]) hd++;
while (hd <= tl && w(q[tl]) >= w(x)) tl--;
q[++tl] = x;
f[x] = w(q[hd]) + x;
L[x * i + y] = min(L[x * i + y], f[x]);
}
}
}
int res = 0;
for (int i = 0; i <= n; i++)
if (L[i] <= R[i]) res += R[i] - L[i] + 1 + ct;
wr(res);
return 0;
}