题解：AT_arc101_c [ARC101E] Ribbons on Tree

Yuneko · 2026-03-23 15:18:57 · 题解

题目链接

AT_arc101_c [ARC101E] Ribbons on Tree

解题思路 & 参考代码

考虑容斥，钦定没被覆盖到的边集为 S，然后给每个联通块的点两两配对，可得方案数 g(S)，答案即为 \displaystyle\sum_{S \subseteq E}^{} (-1)^{|S|}g(S)。

考虑一个大小为 2x 的联通块的点两两配对的方案数，考虑第一个点的选点匹配方案数是 2x - 1，去掉被选择的点后第二个点的选点匹配方案数是 2x - 3 \dots，依次类推，方案数为 \displaystyle\prod_{i=1}^{x} (2i-1)。

考虑直接 dp，f_{u,i} 表示 u 子树内 u 所在的联通块大小为 i 的方案数，有以下转移：

• 钦定这条边被断了： f_{u,i} \gets -1 \times f_{u,i} \times f_{v,j} \times g(j)
• 钦定这条边没被断： f_{u,i+j} \gets f_{u,i} \times f_{v,j}

答案为 \displaystyle\sum_{i=1}^{n} f_{1,i} \times g(i)，时间复杂度 O(n^2)。

:::info[参考代码]

ll n,ans;
ll x,y;
ll f[5010][5010],g[5010],h[5010];
vector<ll>G[5010];
ll sz[5010];
void Dfs(ll x,ll fa)
{
    sz[x]=f[x][1]=1;
    for(auto i:G[x])
        if(i!=fa)
        {
            Dfs(i,x);
            forl(j,0,n)
                h[j]=0;
            forl(j,1,sz[x])
                forl(k,1,sz[i])
                    add(h[j],-f[x][j]*f[i][k]%mod*g[k]%mod),
                    add(h[j+k],f[x][j]*f[i][k]%mod);
            sz[x]+=sz[i];
            forl(j,0,n)
                f[x][j]=h[j];
        }
}
void solve()
{
    g[0]=1;
    forll(i,2,5000,2)
        g[i]=g[i-2]*(i-1)%mod;
    cin>>n;
    forl(i,2,n)
        cin>>x>>y,
        G[x].pb(y),
        G[y].pb(x);
    Dfs(1,0);
    forl(i,1,n)
        ans+=f[1][i]*g[i]%mod;
    cout<<ans%mod<<endl;
}

:::