专栏文章

题解：P4582 [FJOI2014] 树的重心

PPengzt
P4582题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqauhbf
此快照首次捕获于
2025/12/04 01:47
3 个月前
此快照最后确认于
2025/12/04 01:47
3 个月前
查看原文

树的重心

题目链接。cnblogs。luogu。

Problem

有 TT（T≤50T \le 50）组测试数据。
每次给出 nn（≤200\le 200）个节点的树，求它的连通子图数量，使得它的重心与整棵树的重心重合。答案对质数 PP 取模。

Sol

不妨设 did_i 表示以 uu 为根的时候，ii 的子树大小。
先找到树的重心。发现只有 max⁡di=n2\max d_i = \frac n2 的时候才会出现两个重心。
  • 只有一个重心：
不妨记这个重心为 rtrt，
令 fu,if_{u, i} 表示 uu 子树中，连通子图大小为 ii 的数量。
有转移：fu,i′=∑j=0szvfu,i−j⋅fv,jf'_{u, i} = \sum\limits_{j = 0}^{sz_v} f_{u, i - j}\cdot f_{v, j}。然后 f←f′f\gets f'。
uu 做完之后 fu,i←fu,i−1′f_{u, i}\gets f'_{u, i - 1}。最后 ∀u≠rt,fu,0=1\forall u \ne rt, f_{u, 0} = 1。然后初始的时候 ∀u∈leaf,fu,1=1\forall u\in \text{leaf}, f_{u, 1} = 1。这里由于第二维是 O(szv)\mathcal{O}(sz_v) 的，所以这部分的时间复杂度为 O(n2)\mathcal{O}(n^2)。
当 uu 为根的时候，记连通块大小为 szsz，那么要统计 max⁡di<sz2\max d_i < \frac{sz}2 的答案，这个东西其实不是很好统计，但是发现 ≥sz2\ge \frac{sz}2 的儿子很少，考虑统计 max⁡di>sz−12\max d_i > \frac{sz - 1}2 的数量。令 gv,ig_{v, i} 表示不考虑 vv 这个儿子和 uu，连通块大小为 ii 的方案数。则答案为 ∑i=1szvfv,i⋅∑j=0i−1gv,j\sum \limits_{i = 1}^{sz_v} f_{v, i} \cdot \sum \limits_{j = 0}^{i - 1} g_{v, j}。然后就是求出 gu,ig_{u, i}。不难发现 gg 可以表示为一个前缀和后缀的并，这个前后缀的预处理是可以 O(n⋅∑szv)=O(n2)\mathcal{O}(n\cdot\sum sz_v) = \mathcal{O}(n^2) 的。直接暴力合并出 gg 的话是 O(n3/n2log⁡)\mathcal{O}(n^3 / n^2\log) 的，但是发现 gg 只有前 szvsz_v 项有用，所以合并就变为 O(∑szv2)=O(n2)\mathcal{O}(\sum sz_v^2) = \mathcal{O}(n^2) 的了。
  • 两个重心：
把 (rt1,rt2)(rt_1, rt_2) 断开，然后分别以 rt1rt_1，rt2rt_2 为根跑一遍。然后答案为 ∑frt1,i⋅frt2,i\sum f_{rt_1, i}\cdot f_{rt_2, i}。
时间复杂度 O(n2)\mathcal{O}(n^2)。
具体实现可以参考代码，感觉已经很清楚了。

Code

CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
mt19937_64 eng(time(0) ^ clock());
template <typename T>
T rnd(T l, T r) { return eng() % (r - l + 1) + l; }
const int P = 10007;
int n, rt1, rt2;
vector<int> e[205];
int sz[205], mx[205];
void DFS(int u, int ff) {
	sz[u] = 1;
	for (int v : e[u])
		if (v != ff) {
			DFS(v, u);
			sz[u] += sz[v];
			mx[u] = max(mx[u], sz[v]);
		}
	mx[u] = max(mx[u], n - sz[u]);
	if (!rt1 || mx[u] < mx[rt1])
		rt1 = u, rt2 = 0;
	else if (mx[u] == mx[rt1])
		rt2 = u;
}
int f[205][205], g[205][205], pre[205][205], suf[205][205], temp[205];
void Work(int u, int ff) {
	sz[u] = 1;
	int son = 0;
	f[u][0] = 1;
	for (int v : e[u])
		if (v != ff) {
			++son;
			Work(v, u);
			memset(temp, 0, sizeof (temp));
			sz[u] += sz[v];
			for (int i = 0; i <= sz[u]; i++)
				for (int j = 0; j <= min(sz[v], i); j++)
					(temp[i] += f[u][i - j] * f[v][j]) %= P;
			memcpy(f[u], temp, sizeof (f[u]));
		}
	for (int i = sz[u]; i; --i) f[u][i] = f[u][i - 1];
	f[u][0] = 1;
	if (!son) f[u][1] = 1;
}
int ans;
void Solve(int test) {
	memset(f, 0, sizeof (f)), memset(g, 0, sizeof (g)), memset(pre, 0, sizeof (pre)), memset(suf, 0, sizeof (suf)), memset(mx, 0, sizeof (mx));
	rt1 = rt2 = 0;
	scanf("%d", &n);
	for (int i = 1, u, v; i < n; i++)
		scanf("%d%d", &u, &v), e[u].emplace_back(v), e[v].emplace_back(u);
	DFS(1, 0);
	if (rt2) {
		Work(rt1, rt2);
		Work(rt2, rt1);
		ans = 0;
		for (int i = 1; i <= n / 2; i++)
			(ans += f[rt1][i] * f[rt2][i]) %= P;
		printf("Case %d: %d\n", test, ans);
		for (int i = 1; i <= n; i++) e[i].clear();
		return;
	}
	ans = 1;
	Work(rt1, 0);
	for (int i : e[rt1]) {
		int s = 0;
		for (int j = 0; j <= n; j++)
			(s += f[i][j]) %= P;
		(ans *= s) %= P;
	}
	pre[0][0] = 1;
	int len = (int)e[rt1].size();
	for (int i = 0; i < len; i++) {
		int v = e[rt1][i];
		for (int j = 0; j <= n; j++)
			for (int k = 0; k <= min(sz[v], j); k++)
				(pre[i + 1][j] += pre[i][j - k] * f[v][k]) %= P;
	}
	suf[len + 1][0] = 1;
	for (int i = len - 1; i >= 0; --i) {
		int v = e[rt1][i];
		for (int j = 0; j <= n; j++)
			for (int k = 0; k <= min(sz[v], j); k++)
				(suf[i + 1][j] += suf[i + 2][j - k] * f[v][k]) %= P;
	}
	for (int i = 1; i <= len; i++) {
		int v = e[rt1][i - 1];
		for (int j = 0; j <= sz[v]; j++)
			for (int k = 0; k <= j; k++)
				(g[i][j] += pre[i - 1][j - k] * suf[i + 1][k]) %= P;
		for (int j = 1; j <= sz[v]; j++)
			(g[i][j] += g[i][j - 1]) %= P;
		for (int j = 1; j <= sz[v]; j++)
			(ans -= f[v][j] * g[i][j - 1]) %= P;
	}
	(ans += P) %= P;
	printf("Case %d: %d\n", test, ans);
	for (int i = 1; i <= n; i++) e[i].clear();
}
int main() {
	int T;
	scanf("%d", &T);
	for (int i = 1; i <= T; i++)
		Solve(i);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...