题解：CF2182G Short Garland

· · 题解

题解：CF2182G Short Garland

题目要求每次选择与当前点集相邻的点中 dep 值最大的点。这等价于：一旦选择进入一棵子树，就会先把这棵子树走完，再去走其他子树；并且要求连续选择的两点间距离不超过 k。

设走完一棵子树后最后一个点的 dep 值为 x，则从该点回到 u 再进入 u 的其它子树时，所需距离为 x - dep_u + 1。因此只需关心走完该子树后最后一个点的 dep 值。

设计 dp_{u,j} 表示走完 u 子树后最后一个点的 dep 值为 j 的方案数，m 表示 u 的儿子个数。

状态转移

对节点 u 和状态 j，有

dp_{u,j}=(m-1)!\sum_{v\in son_u}dp_{v,j} \prod_{\substack{w\in son_u\\ w\ne v}}s_w s_v=\sum_{x\le r}dp_{v,x},\qquad r=\min(n,\,k+dep_u-1)

这里 (m-1)! 表示：除最后走的子树 v 外，其余 m-1 棵子树的访问顺序数；s_v 表示走完 v 子树且满足距离约束的方案数。

对于非最后走的子树 w，走完后还要回到 u 再进入下一棵子树，因此其最后一个点的深度 x 需满足

x-dep_u+1\le k

即

x\le k+dep_u-1

同时 x\le n，故 r = \min(n, k + dep_u - 1)。注意这里的 r 由当前节点 u 决定。

对每个 u，乘积

\prod_{\substack{w\in son_u\\ w\ne v}}s_w

可以通过前缀积和后缀积 O(m) 预处理，之后每个儿子 v 对应的值可 O(1) 取得。记其为 p_v：

p_v=\prod_{\substack{w\in son_u\\ w\ne v}}s_w

于是

dp_{u,j}=(m-1)!\sum_{v\in son_u}dp_{v,j}\cdot p_v

因此可以对每个点建一棵动态开点线段树维护 dp。合并时，对每个儿子 v，先将 v 的线段树整体乘上 p_v，再合并到 u；合并完所有儿子后，再将 u 的线段树整体乘上 (m-1)!。

时间复杂度证明（线段树合并儿子）

  1. 每个叶子信息插入时，会新建 O(\log n) 个线段树节点（值域大小不超过 n）。 总共不超过 n 个叶子，所以初始节点总数是 O(n\log n)。

  2. 合并两棵线段树时：

:::info[参考代码（C++）]


#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,k;
vector<int>eg[300005];
int tot=0,rt[300005],cnt[300005],dep[300005];
int pre[300005],bak[300005];
const int mod=998244353;
struct tree{
    int l,r,cnt,mul;
}tr[10000005];
int add()
{
    tot++;
    tr[tot].l=tr[tot].r=tr[tot].cnt=0;tr[tot].mul=1;
    return tot;
}
void uplz(int p,int b)
{
    if(!p) return;
    tr[p].cnt=tr[p].cnt*b%mod;
    tr[p].mul=tr[p].mul*b%mod;
}
void pushdown(int p)
{
    if(tr[p].mul!=1)
    {
        uplz(tr[p].l,tr[p].mul);
        uplz(tr[p].r,tr[p].mul);
        tr[p].mul=1;
    }
}
void modify(int &p,int l,int r,int opt,int val)
{
    if(!p) p=add();
    if(l==r)
    {
        tr[p].cnt=(tr[p].cnt+val)%mod;
        return;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(opt<=mid) modify(tr[p].l,l,mid,opt,val);
    else modify(tr[p].r,mid+1,r,opt,val);
    tr[p].cnt=(tr[tr[p].l].cnt+tr[tr[p].r].cnt)%mod;
}
int merge(int u,int v)
{
    if(!u||!v) return u+v;
    pushdown(u);pushdown(v);
    if(tr[u].l==0&&tr[u].r==0)
    {
        tr[u].cnt=(tr[u].cnt+tr[v].cnt)%mod;
        return u;
    }
    tr[u].l=merge(tr[u].l,tr[v].l);
    tr[u].r=merge(tr[u].r,tr[v].r);
    tr[u].cnt=(tr[tr[u].l].cnt+tr[tr[u].r].cnt)%mod;
    return u;
}
int query(int p,int l,int r,int ql,int qr)
{
    if(!p) return 0;
    if(l>=ql&&r<=qr) return tr[p].cnt;
    int mid=(l+r)>>1,now=0;
    pushdown(p);
    if(qr>mid) now=query(tr[p].r,mid+1,r,ql,qr);
    if(ql<=mid) now=(now+query(tr[p].l,l,mid,ql,qr))%mod;
    return now;
}
void dfs(int u)
{
    if(eg[u].size()==0) modify(rt[u],0,n,dep[u],1);
    else
    {
        int m=eg[u].size(),jc=1;
        for(int i=2;i<m;i++) jc=jc*i%mod;
        for(int v:eg[u]) 
        {
            dep[v]=dep[u]+1;
            dfs(v); 
        }
        for(int i=0;i<(int)eg[u].size();i++)
        {
            int v=eg[u][i];
            pre[i]=(i==0?cnt[v]:pre[i-1]*cnt[v])%mod;
        }
        for(int i=eg[u].size()-1;i>=0;i--)
        {
            int v=eg[u][i];
            bak[i]=(i==(int)eg[u].size()-1?cnt[v]:bak[i+1]*cnt[v])%mod;
        }
        for(int i=0;i<eg[u].size();i++)
        {
            int v=eg[u][i];
            int k=1;
            if(i>0) k=k*pre[i-1]%mod;
            if(i+1<eg[u].size()) k=k*bak[i+1]%mod;
            uplz(rt[v],k);
        }
        for(int v:eg[u]) rt[u]=merge(rt[u],rt[v]);
        uplz(rt[u],jc);
    }
    if(u!=1)
    {
        int K=min(n,k+dep[u]-2);
        if(K<0) cnt[u]=0;
        else cnt[u]=query(rt[u],0,n,0,K);
    }
}
void solve()
{
    cin>>n>>k;
    tot=0;
    for(int i=1;i<=n;i++)
    {
        cnt[i]=0;
        rt[i]=0;
        eg[i].clear();
    }
    for(int i=2,f;i<=n;i++)
    {
        cin>>f;
        eg[f].push_back(i);
    }
    dfs(1);
    int ans=query(rt[1],0,n,0,n);
    cout<<ans<<"\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--) solve();
    return 0;
}