Comet OJ

分析

可以发现一个点集的所有直径的中点都相同。为了方便我们把边也拆成点，这样子中点一定是一个点。

枚举中点和半径，那么深度小于半径的点任意选，深度等于半径的必须有至少两棵子树中选了，容斥一下即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=4000+10;
const int mod=998244353;

int n,ans[N],pw[N];
vector<int> E[N];

int tot=0,o[N],c[N][N];
void dfs(int u,int f,int d) {
    if (u<=n) ++o[d],++c[tot][d];
    for (int v:E[u]) if (v!=f) dfs(v,u,d+1);
}

int main() {
    n=read();
    for (int i=pw[0]=1;i<=n;++i) pw[i]=(pw[i-1]<<1)%mod;
    for (int i=1;i<n;++i) {
        int u=read(),v=read();
        E[u].emplace_back(i+n),E[i+n].emplace_back(u);
        E[v].emplace_back(i+n),E[i+n].emplace_back(v);
    }
    for (int u=1;u<n<<1;++u) {
        memset(o,0,sizeof(o)),tot=0;
        for (int v:E[u]) ++tot,memset(c[tot],0,sizeof(c[tot])),dfs(v,u,1);
        int s=(u<=n);
        for (int i=1;i<n;++i) {
            int r=pw[o[i]]-1;
            for (int j=1;j<=tot;++j) r=(r-pw[c[j][i]]+1+mod)%mod;
            ans[i]=(ans[i]+1ll*r*pw[s])%mod;
            s+=o[i];
        }
    }
    for (int i=1;i<n;++i) printf("%d\n",ans[i]);
    return 0;
}