思路：
函数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]);
}
原文：https://www.cnblogs.com/pkgunboat/p/10780978.html