题解：CF1517F Reunion

· · 题解

更好的阅读体验

这也太难了，根本不会啊。

首先把贡献为 -1 的改成 0，为 n 的改成 n-1，这样就不用特判。然后乘上 2^n，转为求方案数。

我们假设点集 S 的价值为 f(S)。那么我们要求的是

\sum _S f(S) = \sum_{r = 0}^{n - 1}r \sum_S [f(S)=r]

我们觉得 \ge 比恰好等于好做。所以差分，拆贡献变成

\sum_{r = 0}^{n - 1} \sum_S [f(S) \ge r]

接下来假设有空的是白点，没空的是黑点。那么存在一个点半径为 r，也就是存在一个点 u，离它最近的黑点和他的距离 > r。我们对每个 r 计算这个东西的方案数。

我们假设 f_{u, i} 表示 u 子树内，到 u 最近的黑点到 u 的距离为 i 的方案数。

假设一个点已经满足了子树内的限制，也就是这个点的子树内，离它最近的黑点到它的距离已经超过 r 了，那么我们称这个点是好的。显然只有好的点才能成为最后可能的聚会的中心。所以我们还要对每个好的点看看它在上面，也就是子树外面，能不能满足到黑点的距离 >r 的限制。

所以我们假设 g_{u, i} 表示 u 子树，最深的好点到 u 的距离 = i 的方案数量。我们之所以关心最深的，是因为最深的限制最松，如果最深的都无法达到距离 > r 的限制，那么别的点更不可能达到了。

首先有初始值 f_{u, 0} = g_{u, 0} = 1，如果 u 被选中为黑点就是赋值给 f_{u, 0}，如果 u 是白点那么 u 就是好的，因此赋值给 g_{u, 0}。

那么考虑转移，下文中 v 是 u 的儿子。

  1. 合并 f_{u, i}, f_{v, j}：这是简单的，只要分别枚举两个子树内最浅的黑点到 u 的距离 i, j，合并后的距离是 \min(i, j+1)。 f_{u, \min(i, j+1)} \leftarrow f_{u, i} \cdot f_{v, j}
  2. 合并 g_{u, i}, g_{v, j}：同理，枚举两个子树内最深的好点的深度。
g_{u, \max(i, j+1)} \leftarrow g_{u, i} \cdot g_{v, j}
  1. 合并 f_{u, i}, g_{v, j}。如果 j+1+i \le r，说明 g 子树内的好点全部被 u 子树内的黑点击落了，所以转移到 f_{u, i}，否则 v 子树的好点不变，转移到 g_{u, j+1}。
f_{u, i} \leftarrow [j + i + 1 \le r]f_{u, i} \cdot g_{v, j} g_{u, j+1} \leftarrow [j + i + 1 > r]f_{u, i} \cdot g_{v, j}
  1. 合并 g_{u, i}, f_{v, j}。同 3，如果 j+1+i \le r，说明 u 子树内的好点全部被 v 子树内的黑点击落了，所以转移到 f_{v, j+1}，否则转移到 g_{u, i}。
f_{u, j+1} \leftarrow [j + i + 1 \le r]g_{u, i}\cdot f_{v, j} g_{u, i} \leftarrow [j + i + 1 > r]g_{u, i}\cdot f_{v, j}

我们首先枚举 r，然后跑这个 dp。发现 f_{u, i} 和 g_{u, i} 的 i 都是 O(\operatorname{size}_u) 级别的，所以可以做到树上背包的复杂度，单个 r 可以 O(n^2)。

最后记得除以 2^n。

那么这道题就做完了，复杂度 O(n^3)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 306
#define MOD 998244353
using namespace std;
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;}
int n,ans,sz[N],f[N][N],g[N][N],tf[N],tg[N];
vector<int> G[N];
void dfs(int u,int fa,int r)
{
    f[u][0]=g[u][0]=sz[u]=1;
    for(int v:G[u])if(v!=fa)
    {
        dfs(v,u,r);
        for(int i=0;i<=sz[u];i++)
            for(int j=0;j<=sz[v];j++)
        {
            add(tf[min(i,j+1)],1ll*f[u][i]*f[v][j]%MOD);
            add(tg[max(i,j+1)],1ll*g[u][i]*g[v][j]%MOD);
            if(i+j+1>r)
            {
                add(tg[i],1ll*g[u][i]*f[v][j]%MOD);
                add(tg[j+1],1ll*f[u][i]*g[v][j]%MOD);
            } else {
                add(tf[i],1ll*f[u][i]*g[v][j]%MOD);
                add(tf[j+1],1ll*g[u][i]*f[v][j]%MOD);
            }
        }
        for(int i=0;i<=sz[u]+sz[v];i++)
            f[u][i]=tf[i],tf[i]=0,g[u][i]=tg[i],tg[i]=0;
        sz[u]+=sz[v];
    }
}
int solve(int r)
{
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    dfs(1,0,r); int ret=0;
    for(int i=0;i<n;i++)add(ret,g[1][i]);
    return ret;
}
main()
{
    scanf("%d",&n);
    for(int i=1,u,v;i<n;i++)
        scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
    for(int i=1;i<n;i++)add(ans,solve(i));
    for(int i=1;i<=n;i++)ans=499122177ll*ans%MOD;
    printf("%d\n",ans);
    return 0;
}