P7565 [JOISC 2021] ビーバーの会合 2 (Day3) - Solution

刚开始想了一个假贪心还觉得对完了。

首先，可期待点类似于树的重心，不过这是虚树的重心。

给出一个重要观察：可期待点构成树上的一条链。

两个可期待点之间的点均可期待。

否则，取出该不可期待点，该点必定存在一个子树，关键点数大于它的其余子树之和。而两个可期待点至少有一个不在该子树中，该可期待点往这个子树方向走贡献变小，矛盾。

不存在度数 $\ge 3$ 的可期待点（这里的度数仅计算可期待点与可期待点之间）。

注意到我们取出该点（关键点意义下）最小的可期待点子树，走到该点贡献变小，矛盾。

既然可期待点构成树上的一条链，很显然可以考虑点分治。

具体到点分治上，设当前点分治的根为

x

。我们不妨枚举一端

u

。

假设要求关键点数为

k

，我们钦定路径

u \to v

。如果我们可以把

\frac{k}{2}

塞进

u

子树里面，把

\frac{k}{2}

塞进

v

子树里面，那么这就构造出了一种合法方案。否则，我们肯定没办法构造出来另一种方案，因为不管怎么样，我们都不能在三个方向上同时布满关键点，还让

u \to v

有贡献。

然后我们相当于

sz_u \ge \frac{k}{2}

就可能贡献到

k

上，这个东西我们可以直接搞成后缀最大值，并且考虑与前面的某个满足相同条件的

v

合并。

时间复杂度

\Theta(n \log n)

。

CPP

int n; vec<int> g[maxn]; int vis[maxn], rt, sz[maxn], W, S, d[maxn], ans[maxn];
void getrt(int u, int f = 0) {
	sz[u] = 1; int x = 0;
	for (int v : g[u]) {
		if (v == f || vis[v]) continue;
		getrt(v, u), sz[u] += sz[v];
		if (sz[v] > sz[x]) x = v;
	}
	int k = max(sz[x], S - sz[u]);
	if (k < W) rt = u, W = k;
}
int s[maxn], t[maxn];
void dfs(int u, int f) {
	d[u] = d[f] + 1; 
	for (int v : g[u]) if (!vis[v] && v != f) dfs(v, u);
	s[sz[u]] = max(s[sz[u]], d[u]);
}
void calc(int u) {
	vis[u] = 1; d[u] = 0; getrt(u, 0);
	for (int v : g[u]) {
		if (vis[v]) continue;
		dfs(v, u);
		per(i, sz[v] - 1, 1) s[i] = max(s[i], s[i + 1]);
		rep(i, 1, sz[v]) ans[i * 2] = max(ans[i * 2], s[i] + t[i]);
		rep(i, 1, sz[v]) t[i] = max(t[i], s[i]), s[i] = 0;
	}
	rep(i, 1, sz[u]) s[i] = t[i] = 0;
	for (int v : g[u]) {
		if (vis[v]) continue;
		rt = 0, S = sz[v], W = 1e9;
		getrt(v, u); calc(rt);
	}
}
int main() {
	scanf("%d", &n); 
	if (n == 1) puts("1"), exit(0);
	for (int i = 1, u, v; i < n; i++) scanf("%d%d", &u, &v), g[u].pb(v), g[v].pb(u);
	rt = 0, S = n, W = 1e9; getrt(1, 0); calc(rt);
	rep(i, 1, n) printf("%d\n", (i & 1) ? 1 : ans[i] + 1);
	return 0;
}

P7565 [JOISC 2021] ビーバーの会合 2 (Day3) - Solution

文章操作

相关推荐

评论

P7565 [JOISC 2021] ビーバーの会合 2 (Day3) - Solution