P5281 zjoi2019minimax搜索

考虑求稳定度恰好是k的并不方便,于是转而求稳定度小于等于k的做差分即可
首先考虑暴力
考虑如何O(n)求稳定度小于等于k的方案数
因为每个叶子结点的权值都不同,所以最终转移到根的一定是唯一的一条链,称为答案链
而只要通过修改答案链上某个点子树中其他叶节点使链上这个点权值改变,就会使根节点权值改变
我们要求有多少个集合在稳定度小于等于k时可以让链上的点权值改变,可以通过求有多少个集合不可以让链上点权值改变,用总数减掉即可
由于链上的点有奇深度也有偶深度,所以分开考虑
先考虑奇数深度的,偶数同理
设val为当前根节点权值,delt为当前考虑的稳定度,cnt[i]为i子树中2^{叶子节点个数}
设dp[i]表示考虑i的子树,有多少种集合满足使i的权值<=val(即不会改变链权值)
当i为叶子时,dp[i]=(i<=val)+(i+delt<=val)
当i深度为奇数时,i的所有儿子都要满足条件,所以dp[i]=\prod_{j\in son[i]}dp[j]
当i深度为偶数时,只要一个儿子满足就可以,所以用总的减掉不合法的dp[i]=cnt[i]-\prod_{j\in son[i]}(cnt[j]-dp[j])
最终的答案就是所有链上点子树dp值的乘积

考虑对这个dp进行优化
发现改变delt时,每个叶子节点的dp值只会改变一次,而改变后就会相应影响其上方的点的dp值,非常像动态dp
为了方便动态dp的转移,我们定义dp'
同样的先考虑奇数深度的链上的点
由于最终答案是链上这个点儿子dp值的乘积,所以这个点儿子的dp'就等于dp
而与这个点儿子节点深度奇偶性相同的点dp'=dp,不同的点dp'=cnt-dp
于是转移就变得相同dp'[i]=cnt[i]-\prod_{j\in son[i]}dp'[j],方便维护
由于稳定度为0时许多叶子点的dp为0,而在改变其权值时需要除掉原来的dp值,不方便
所以稳定度从大往小考虑
动态dp的细节:
点i和他重儿子zson[i]dp'值的关系可以看做dp'[i]=k*dp'[zson[i]]+b,其中k=-\prod_{j\in son[x],j!=zson[x]}dp'[j],b=cnt[i]
这个东西本质上是矩阵乘法,但是{k1,b1} {k2,b2}={k1 k2,k1*b2+b1}可以减小常数
另外要注意,判叶子节点不能只判出边个数为1,还要判不是根节点
代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int mod=998244353;
int kpow(int a,int b)
{
    int s=1;
    while(b)
    {
        if(b&1)s=1ll*s*a%mod;
        b>>=1;
        a=1ll*a*a%mod;
    }
    return s;
}
int mdf[200020][3];
struct bian
{
    int to,nxt;
}bi[400040];
int n,head[200020],num,l,r,depth[200020],va[200020],cnt[200020],ans[200020];
int siz[200020],zson[200020],tp[200020],f[200020],id[200020],dy[200020],idnum,ed[200020],rt[200020];
int dp[200020],Ans=1;
bool type[200020],flag;
struct data
{
    int k,b;
    data(int kk=0,int bb=0){k=kk,b=bb;}
    friend data operator * (data a,data b){return data(1ll*a.k*b.k%mod,(1ll*a.k*b.b+a.b)%mod);}
}tr[800080],p[200020];
void add(int from,int to)
{
    bi[++num].nxt=head[from];
    head[from]=num;
    bi[num].to=to;
}
void predfs(int v,int fa)
{
    depth[v]=depth[fa]+1;f[v]=fa;siz[v]=1;
    if(!bi[head[v]].nxt&&v!=1)
    {
        va[v]=v,cnt[v]=2;
        return ;
    }
    int u;va[v]=depth[v]&1?1:n;cnt[v]=1;
    for(int i=head[v];i;i=bi[i].nxt)
    {
        u=bi[i].to;
        if(u==fa)continue;
        predfs(u,v);
        siz[v]+=siz[u];
        if(siz[u]>siz[zson[v]])zson[v]=u;
        cnt[v]=1ll*cnt[v]*cnt[u]%mod;
        if(depth[v]&1)va[v]=max(va[v],va[u]);
        else va[v]=min(va[v],va[u]);
    }
}
int getdp(int v,int fa,int topp,int RT)
{
    rt[v]=RT,id[v]=++idnum,dy[idnum]=v,tp[v]=topp;
    if(!bi[head[v]].nxt&&v!=1)
    {
        if(type[RT])
        {
            dp[v]=p[v].k=(depth[v]&1)?2-(v<=va[1]):(v<=va[1]);
            if(v<=va[1])mdf[va[1]-v][++mdf[va[1]-v][0]]=v;
        }
        else
        {
            dp[v]=p[v].k=(depth[v]&1)?(v>=va[1]):2-(v>=va[1]);
            if(v>=va[1])mdf[v-va[1]][++mdf[v-va[1]][0]]=v;
        }
        ed[topp]=idnum;
        return dp[v];
    }
    int u,ret=mod-1;
    dp[v]=getdp(zson[v],v,topp,RT);
    for(int i=head[v];i;i=bi[i].nxt)
    {
        u=bi[i].to;
        if(u==fa||u==zson[v])continue;
        ret=1ll*ret*getdp(u,v,u,RT)%mod;
    }
    p[v]=data(ret,cnt[v]),(dp[v]=cnt[v]+1ll*dp[v]*ret%mod)>=mod?dp[v]-=mod:0;
    return dp[v];
}
void dfs(int v,int fa)
{
    int ret=1,u;
    for(int i=head[v];i;i=bi[i].nxt)
    {
        u=bi[i].to;
        if(u==fa)continue;
        if(va[u]==va[v])dfs(u,v);
        else f[u]=0,type[u]=depth[v]&1,Ans=1ll*Ans*getdp(u,v,u,u)%mod;
    }
//  printf("%d %d\n",v,ret);
}
void build(int k,int l,int r)
{
    if(l==r)
    {
        tr[k]=p[dy[l]];
        return ;
    }
    build(k<<1,l,l+r>>1),build(k<<1|1,(l+r>>1)+1,r);
    tr[k]=tr[k<<1]*tr[k<<1|1];
}
void upd(int k,int l,int r,int pos)
{
    if(l==r)
    {
        tr[k]=p[dy[l]];
        return ;
    }
    if(pos<=l+r>>1)upd(k<<1,l,l+r>>1,pos);
    else upd(k<<1|1,(l+r>>1)+1,r,pos);
    tr[k]=tr[k<<1]*tr[k<<1|1];
}
data query(int k,int l,int r,int ll,int rr)
{
    if(l>=ll&&r<=rr)return tr[k];
    if(rr<=(l+r>>1))return query(k<<1,l,l+r>>1,ll,rr);
    if(ll>(l+r>>1))return query(k<<1|1,(l+r>>1)+1,r,ll,rr);
    return query(k<<1,l,l+r>>1,ll,rr)*query(k<<1|1,(l+r>>1)+1,r,ll,rr);
}
void modify(int x)
{
//  if(flag)printf("%d\n",x);
    int RT=rt[x];
    Ans=1ll*Ans*kpow(dp[RT],mod-2)%mod;
    p[x].k=(type[RT]^(depth[x]&1))?2:0;
    upd(1,1,idnum,id[x]);
    while(f[tp[x]])
    {
    //  if(flag)printf("%d\n",x);
        int fa=f[tp[x]];
        p[fa].k=1ll*p[fa].k*kpow(dp[tp[x]],mod-2)%mod;
        data s=query(1,1,idnum,id[tp[x]],ed[tp[x]]);
        (dp[tp[x]]=s.k+s.b)>=mod?dp[tp[x]]-=mod:0;
        p[fa].k=1ll*p[fa].k*dp[tp[x]]%mod;
        upd(1,1,idnum,id[fa]);
        x=fa;
    }
    data s=query(1,1,idnum,id[RT],ed[RT]);
    (dp[RT]=s.k+s.b)>=mod?dp[RT]-=mod:0;
    Ans=1ll*Ans*dp[RT]%mod;
}
int main()
{
    scanf("%d %d %d",&n,&l,&r);
    int x,y;
    for(int i=1;i<n;++i)
    {
        scanf("%d %d",&x,&y);
        add(x,y),add(y,x);
    }
    predfs(1,0);
    dfs(1,0);
//    printf("%d\n",mdf[1][1],mdf[1][2]);
    build(1,1,idnum);
 //   printf("%d ",mdf[1][0]);
    for(int i=n-1;i;--i)
    {
        if(i==1)flag=1;
        for(int u=1;u<=mdf[i][0];++u)modify(mdf[i][u]);
        (ans[i]=cnt[1]+mod-Ans)>=mod?ans[i]-=mod:0;
    //  printf("%d\n",i);
    }
    ans[n]=cnt[1]-1;
    for(int i=l;i<=r;++i)
        printf("%d ",ans[i]-ans[i-1]<0?ans[i]-ans[i-1]+mod:ans[i]-ans[i-1]);
    return 0;
}