Comet OJ - Contest #2 D 枚举重心

思路：

函数f相当于是求一个点集f的直径，有一个性质是如果这个点集有多个直径一定相交于某一个点，或者一条边的中心，所以我们暴力枚举重心，计算以某个点为重心的点集对答案的贡献。

具体实现的时候，我们从一个重心开始深搜，计算其它点到这个点的距离。我们现在假设计算以当前点为重心，有多少个点集的直径是i。首先，之前所有半径小于i / 2的点随便选了，假设有sum个，那前面的点有2 ^ sum种情况。假设半径是i / 2的点有cnt[i]个，那只有这些点才可能构造出i的直径，并且，这两个点不能在一个连通块中(把重心去掉后可能会形成若干个连通块), 所以我们枚举每个连通块中半径是i / 2的点数，此时假设其它连通块中没有点半径是i / 2，减去这些情况就可以了。

代码：

#include <bits/stdc++.h>

#define LL long long

using namespace std;

const int maxn = 4010;

const LL mod = 998244353;

int head[maxn], Next[maxn * 2], ver[maxn * 2], tot;

LL cnt[maxn], re[maxn][maxn], p[maxn], ans[maxn];

int n;

void add(int x, int y) {

	ver[++tot] = y;

	Next[tot] = head[x];

	head[x] = tot;

}

void dfs(int x, int fa, int deep, int dye) {

	if(x <= n) {

		cnt[deep]++;

		re[dye][deep]++;

	}

	for (int i = head[x]; i; i = Next[i]) {

		int y = ver[i];

		if(y == fa) continue;

		dfs(y, x, deep + 1, dye);

	}

}

int main() {

	int x, y;

	scanf("%d", &n);

	for (int i = 1; i < n; i++) {

		scanf("%d%d", &x, &y);

		add(x, i + n), add(i + n, x), add(y, i + n), add(i + n, y);

	}

	p[0] = 1;

	for (int i = 1; i <= 2 * n - 1; i++) p[i] = (p[i - 1] * 2) % mod;

	for (int i = 1; i <= 2 * n - 1; i++) {

		int dye = 0;

		LL sum = 0;

		memset(cnt, 0, sizeof(cnt));

		if(i <= n) {

			cnt[0]++;

			sum = 1;

		}

		for (int j = head[i]; j; j = Next[j]) {

			int y = ver[j];

			dye++;

			memset(re[dye], 0, sizeof(re[dye]));

			dfs(y, i, 1, dye);

		}

		for (int j = 1; j < n; j++) {

			LL now = p[cnt[j]] - 1;

			for (int k = 1; k <= dye; k++)

				now = (now - (p[re[k][j]] - 1) + mod) % mod;

			ans[j] = (ans[j] + (now * p[sum]) % mod) % mod;

			sum += cnt[j];

		}

	}

	for (int i = 1; i < n; i++)

		printf("%lld\n", ans[i]);

}

巴特西

Comet OJ - Contest #2 D 枚举重心

最新文章

热门文章