526互联

AtCoder Regular Contest 125 F Tree Degree Subset Sum

发布时间 2023-05-03 15:10:11作者: zltzlt

洛谷传送门

AtCoder 传送门

首先将度数 \(-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;
}