题解：P17316 [KismetOI 2026 I] 孤独绽放的彼岸花

· · 题解

题意简述

给定一棵以 1 为根的树，边权是未知的非负整数。所有点到根的距离均不超过 X。在所有合法边权方案中，求存在深度至少为 k、距离不超过 S 的点的概率。

解题思路

令 d_u 表示根到 u 的距离。每条边 (\operatorname{fa}_u,u) 的权值等于 d_u-d_{\operatorname{fa}_u}。因此，边权方案与满足下列条件的距离标号一一对应：

\begin{aligned} d_1 & =0 \\ 0\le d_{\operatorname{fa}_u} & \le d_u\le X \end{aligned}

把不降关系反向会更便于计数。令 b_u=X-d_u，则 b_1=X，并且每个儿子的 b 值不超过父亲。

若某个深度大于 k 的点满足体力限制，它在根路径上的祖先也满足限制。取其中深度为 k 的祖先即可。反向包含关系直接成立。因此，只需判断是否存在深度恰为 k 且 d_u\le S 的点。

先计算全部合法局面。对非根节点 u，定义 F_u(t) 为在 0\le b_u\le t 时，u 的子树内共有多少种单调标号。枚举 b_u=r 可得：

F_u(t)=\sum_{r=0}^t\prod_{v\in\operatorname{son}_u}F_v(r)

根节点的值固定为 X，不需要再对它求前缀和。因此总方案数为：

C(X)=\prod_{v\in\operatorname{son}_1}F_v(X)

叶子满足 F_u(t)=t+1。对于非叶子，设各儿子的多项式次数上界之和为 q。乘积的次数不超过 q，再求前缀和只增加一次。由子树大小归纳可知，F_u 的次数不超过 \operatorname{siz}_u。

代码计算每个 F_u 在 0,1,\dots,n 的值。横坐标连续，可以用前后缀积在 O(n) 时间内完成单点拉格朗日插值。

再计算事件的补集。补集要求每个深度为 k 的点都满足 d_u>S。令：

L=X-S

补集条件等价于这些点均满足 b_u<L。直接维护整个分段函数并不方便。因此，只对 b_u\ge L 的部分重新建立多项式。

考虑深度不超过 k 的非根节点。令 P_u(r) 表示固定 b_u=r 时，子树满足补集条件的方案数。再定义：

G_u(z)=\sum_{r=0}^{L+z}P_u(r)

若 \operatorname{dep}_u=k，所有 r\ge L 都违反补集条件，而 r<L 时整棵子树已经由 F_u 计数。因此：

G_u(z)=F_u(L-1)

若 \operatorname{dep}_u<k，固定 b_u=L+z 后，每个儿子的值都不超过它。各儿子可以独立选择，所以：

\begin{aligned} P_u(L+z) & =\prod_{v\in\operatorname{son}_u}G_v(z) \\ G_u(z) & =F_u(L-1)+\sum_{i=0}^zP_u(L+i) \end{aligned}

这里仍然只有多项式乘法和前缀和。相同的次数归纳说明 G_u 的次数不超过子树大小。

根节点的 b 值固定为 X=L+S。所以根处只需代入偏移量 S，不再求前缀和。补集方案数为：

B(S)=\prod_{v\in\operatorname{son}_1}G_v(S)

用补集计数除以总方案数，最终答案为：

\frac{C(X)-B(S)}{C(X)}

若树的最大深度小于 k，答案为 0。若 X\le S 且存在深度为 k 的点，答案为 1。

每个多项式保存 n+1 个连续点值，并使用连续点拉格朗日插值。单组数据的时间复杂度为 O(n^2)，空间复杂度为 O(n^2)。

参考代码

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

using ll=long long;
const int N=3005;
const int mod=998244353;
int n,k,mx;
ll s,x,l;
int dep[N],siz[N];
int fac[N],ifac[N],pre[N],suf[N];
int f[N][N],g[N][N];
vector<int> e[N];
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;
}
int calc(int *a,ll x,int d)
{
    x%=mod;
    if(x<=d)return a[x];
    pre[0]=1;
    for(int i=0;i<=d;i++)pre[i+1]=(int)((ll)pre[i]*(x-i+mod)%mod);
    suf[d+1]=1;
    for(int i=d;i>=0;i--)suf[i]=(int)((ll)suf[i+1]*(x-i+mod)%mod);
    ll ans=0;
    for(int i=0;i<=d;i++)
    {
        ll res=(ll)a[i]*pre[i]%mod*suf[i+1]%mod*ifac[i]%mod*ifac[d-i]%mod;
        if((d-i)&1)ans-=res;
        else ans+=res;
    }
    return (int)((ans%mod+mod)%mod);
}
void dfs(int u)
{
    siz[u]=1;
    mx=max(mx,dep[u]);
    for(int i=0;i<=n;i++)f[u][i]=1;
    for(auto v:e[u])
    {
        dep[v]=dep[u]+1;
        dfs(v);
        siz[u]+=siz[v];
        for(int i=0;i<=n;i++)f[u][i]=(int)((ll)f[u][i]*f[v][i]%mod);
    }
    if(u!=1)
    {
        for(int i=1;i<=n;i++)
        {
            f[u][i]+=f[u][i-1];
            if(f[u][i]>=mod)f[u][i]-=mod;
        }
    }
}
void dfs2(int u)
{
    if(dep[u]==k)
    {
        int val=calc(f[u],l-1,siz[u]);
        fill(g[u],g[u]+n+1,val);
        return;
    }
    for(int i=0;i<=n;i++)g[u][i]=1;
    for(auto v:e[u])
    {
        dfs2(v);
        for(int i=0;i<=n;i++)g[u][i]=(int)((ll)g[u][i]*g[v][i]%mod);
    }
    if(u!=1)
    {
        int val=calc(f[u],l-1,siz[u]);
        for(int i=0;i<=n;i++)
        {
            g[u][i]+=i?g[u][i-1]:val;
            if(g[u][i]>=mod)g[u][i]-=mod;
        }
    }
}
void solve()
{
    cin>>n>>k>>s>>x;
    for(int i=1;i<=n;i++)e[i].clear();
    for(int i=2;i<=n;i++)
    {
        int p;
        cin>>p;
        e[p].push_back(i);
    }
    dep[1]=0;
    mx=0;
    dfs(1);
    if(mx<k)
    {
        cout<<0<<'\n';
        return;
    }
    if(x<=s)
    {
        cout<<1<<'\n';
        return;
    }
    l=x-s;
    dfs2(1);
    int all=calc(f[1],x,n);
    int bad=calc(g[1],s,n);
    cout<<(ll)(all-bad+mod)%mod*Pow(all,mod-2)%mod<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    fac[0]=1;
    for(int i=1;i<N;i++)fac[i]=(int)((ll)fac[i-1]*i%mod);
    ifac[N-1]=(int)Pow(fac[N-1],mod-2);
    for(int i=N-1;i;i--)ifac[i-1]=(int)((ll)ifac[i]*i%mod);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}