题解：P16175 [ICPC 2014 NAIPC] Cheats

· · 题解

题意简述

每个目标除根目标外都有一个前置目标。作弊可以让某个目标先于其父亲完成，但仍要晚于祖父；每个目标至多参与一次作弊。求使用不超过 k 次作弊时的合法完成顺序数。

解题思路

前置关系构成一棵以 1 为根的树。固定一种完成顺序。若节点 v 出现在父亲 u 之前，就必须在边 (u,v) 上使用作弊；否则不需要在这条边上作弊。因此，一种顺序所需的作弊边集合是唯一的。

每个节点至多参与一次作弊，等价于所选边构成树上的匹配。

考虑选择边 (u,v)。若 u 不是根，设其父亲为 p。由于相邻边不能同时选择，p 必须先于 u。题目又要求 p 先于 v，而作弊使 v 先于 u，故局部顺序为 p,v,u。

这等价于对树进行一次旋转。让 v 取代 u 成为 p 的儿子，再让 u 成为 v 的儿子。若 u 是根，则让 v 成为新根。匹配中的旋转不会共用端点。全部旋转后仍得到一棵根树。

新树的拓扑序与恰好使用这些作弊的完成顺序一一对应。对根树，设节点 u 的子树大小为 s_u。其拓扑序数量由树形排列公式给出：

L=\frac{n!}{\prod_u s_u}

选择边 (u,v) 后，只有 u,v 的子树大小发生变化。它们由 s_u,s_v 变为：

(s'_v,s'_u)=(s_u,s_u-s_v)

因此，这次旋转使拓扑序数量乘上：

w_{u,v}=\frac{s_v}{s_u-s_v}

先计算原树的拓扑序数量 L。问题就变为计算树上大小不超过 k 的所有匹配，其边权乘积之和；最后再乘 L。

设 f_{u,j,0} 表示 u 的子树内选择了 j 条边，且 u 未与儿子匹配时的权值和。类似地，f_{u,j,1} 表示 u 已与某个儿子匹配。

依次合并儿子 v。若不选择 (u,v)，两种 u 的状态都可以与 v 的两种状态合并。若选择该边，只能由 u,v 均未匹配的状态转移，并额外乘 w_{u,v}。这是普通的树上背包。

所有除法均使用模意义下的逆元。时间复杂度为 O(nk^2)，空间复杂度为 O(nk)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=205;
const int mod=1000000007;
vector<int> g[N];
int siz[N];
ll f[N][N][2];
int lim;
ll Pow(ll x,ll y)
{
    x%=mod;
    ll res=1;
    while(y)
    {
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
void dfs(int u)
{
    siz[u]=1;
    for(int v:g[u])
    {
        dfs(v);
        siz[u]+=siz[v];
    }
    f[u][0][0]=1;
    for(int v:g[u])
    {
        ll nf[N][2]={};
        ll w=(ll)siz[v]*Pow(siz[u]-siz[v],mod-2)%mod;
        for(int i=0;i<=lim;i++)
        {
            for(int j=0;i+j<=lim;j++)
            {
                ll sum=(f[v][j][0]+f[v][j][1])%mod;
                for(int k=0;k<2;k++)nf[i+j][k]=(nf[i+j][k]+f[u][i][k]*sum)%mod;
                if(i+j<lim)nf[i+j+1][1]=(nf[i+j+1][1]+f[u][i][0]*f[v][j][0]%mod*w)%mod;
            }
        }
        for(int i=0;i<=lim;i++)
        {
            f[u][i][0]=nf[i][0];
            f[u][i][1]=nf[i][1];
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while(cin>>n>>lim,n||lim)
    {
        for(int i=1;i<=n;i++)g[i].clear();
        memset(f,0,sizeof(f));
        for(int i=2;i<=n;i++)
        {
            int p;
            cin>>p;
            g[p].push_back(i);
        }
        dfs(1);
        ll base=1;
        for(int i=1;i<=n;i++)
        {
            base=base*i%mod;
            base=base*Pow(siz[i],mod-2)%mod;
        }
        ll ans=0;
        for(int i=0;i<=lim;i++)ans=(ans+f[1][i][0]+f[1][i][1])%mod;
        cout<<base*ans%mod<<'\n';
    }
    return 0;
}