题解：P17859 「GLR-R5」白露 / ros

· · 题解

先考虑一下朴素的 dp。假设当前合法序列的最大值、严格次大值分别是 mx_1,mx_2，如果往序列后面再插入一个 x，什么情况下是合法的。

  1. 如果 x\ge mx_1，那么一定合法。
  2. 如果 x 是 mx_1 的邻居并且 x\ge mx_2，那么一定合法。
  3. 否则就需要满足 x 同时是 mx_1,mx_2 的邻居，显然这样的 x 只会有一个，并且满足剩下所有点的约束要求。

于是就可以设计出来一个朴素的 dp。定义 f_{i,mx_1,mx_2,0/1} 表示当前序列中已经有 i 个数，最大值是 mx_1，严格次大值是 mx_2，mx_1,mx_2 的公共邻居是否是一个合法点。如果接下来选择枚举下一个转移点 x，那么复杂度是 O(n^3m) 的。

考虑优化上面的状态设计。显然这个 mx_2 是没有必要维护的，如果将 mx_1 的邻居降序排序，那么只会是一个前缀部分满足 \ge mx_2 的条件。所以只需要记录 mx_1 的邻居中有多少个点满足 \ge mx_2 的条件。这样直接就把状态数压缩到 O(n) 级别的了。但是还可能有一个特殊的合法邻居，也就是 mx_1,mx_2 的公共邻居，所以还需要把这种情况也记录上。

所以定义 f_{u,k} 表示当前最大值为 u 并且有 k 个 u 的邻居大于等于严格次大值，然后再用 g_{u,k} 记录 f_{u,k} 中仍然有合法“公共邻居”的方案，再加一个 h_{u,j} 表示这个合法“公共邻居”恰好是 u 的第 j 大儿子的方案数。然后考虑状态转移。在这里，我们规定 son_{u,c} 是 u 的第 c 大儿子。

先考虑下一个点选择的是 u 的情况，这显然是合法的，并且最大值和严格次大值都没有变化，所以有：

nf_{u,k}\gets nf_{u,k}+f_{u,k} ng_{u,k}\gets ng_{u,k}+g_{u,k} nh_{u,j}\gets nh_{u,j}+h_{u,j}

再考虑下一个邻居选择“公共邻居”的方案。设这个公共邻居是 x，那么一定有 x<mx_2<mx_1，所以最大值和次大值都不会变化。于是有：

nf_{u,k}\gets nf_{u,k}+g_{u,k} ng_{u,k}\gets ng_{u,k}+g_{u,k} nh_{u,j}\gets nh_{u,j}+h_{u,j}

再考虑选择一个新的严格次大值的情况。假设选定的是 x，并且有 x 是 u 的第 j 大的儿子。那么次大值将会变化，新的状态就是 f_{u,j}，那么如果原来的 f_{u,k} 能转移到新的状态当且仅当 k\ge j，是一段后缀，所以用后缀和优化转移。也就是：

nf_{u,j}\gets nf_{u,j}+suff_{u,j}

在这种情况下，最大值与次大值在树上的距离变成了 1，所以一定不会有公共邻居，h,g 也就不会发生变化。

最后一种就是选择一个新的最大值。为了方便转移，我们再定义一个数组 ok_{u,j} 表示当前最大值为 u 的时候下一步能选择 son_{u,j} 的方案数。显然：

ok_{u,j}=suff_{u,j+1}+h_{u,j}

假设加入的新的最大值是 x，原来的最大值 u 变成了严格次大值。那么对于 f_{x,j} 来说，对应的合法的严格次大值应该是在一个区间内的，并且对于旧状态的次大值是不做要求的。也就是说，定义 sum_u 表示所有最大值为 u 的合法状态，presum 是 sum 的前缀和数组，于是：

nf_{x,j}\gets nf_{x,j}+presum_{r}-presum_{l-1}

其中 [l,r] 是 u 的合法区间。

在这个新的状态中，x,u 可能会有公共邻居，我们需要判断这个公共邻居是否合法。假设原来的序列为 S，公共邻居是 c，那么如果 S+x+c 这个新的序列是合法的，则当且仅当 S+c 是合法的。设 c 在 u 中的位置是 j，那么这种情况的数量就正好是 ok_{u,j}。先令 val_{c,u}=ok_{u,j}，然后再对每个 val_c 做前缀和，就能快速转移了。

这样下来，预处理部分需要二分找位置，所以复杂度是 O(n\log n) 的。dp 部分每轮转移都是 O(n) 的，总复杂度就是 O(n\log n+nm)。但是由于常数很大，还是需要轻微卡常。

::::info[代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,mod=1e9+9;
int T,n,m,sum[N],presum[N],st[N],tot,est[N],ast[N],etot,atot;
int f[2][N<<1],g[2][N<<1],h[2][N<<1],ok[N],pos[N],val[N<<1];
vector<int>adj[N],son[N];
struct Query{int mx,cnt,pos,id,l,r;};vector<Query>qry;
inline int getk(int u,int x){
    int l=0,r=(int)son[u].size()-1,ans=-1;
    while(l<=r){int mid=(l+r)>>1;if(son[u][mid]>=x)l=mid+1,ans=mid;else r=mid-1;}
    return ans+1;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;while(T--){
        cin>>n>>m;qry.clear();for(int i=1;i<=n;i++)adj[i].clear(),son[i].clear();
        for(int i=1;i<n;i++){int u,v;cin>>u>>v;adj[u].push_back(v),adj[v].push_back(u);}
        for(int u=1;u<=n;u++)sort(adj[u].begin(),adj[u].end());
        for(int u=1;u<=n;u++){
            for(auto v:adj[u])if(v<u)son[u].push_back(v);
            sort(son[u].begin(),son[u].end(),greater<int>());
        }
        tot=etot=atot=0;
        for(int u=1;u<=n;u++){
            st[u]=tot,tot+=son[u].size()+1;
            est[u]=etot,etot+=son[u].size();
            ast[u]=atot,atot+=adj[u].size();
        }
        fill(f[0],f[0]+tot,0),fill(g[0],g[0]+tot,0),fill(h[0],h[0]+tot,0);
        for(int u=1;u<=n;u++){
            for(int j=0;j<(int)son[u].size();j++)pos[est[u]+j]=lower_bound(adj[son[u][j]].begin(),adj[son[u][j]].end(),u)-adj[son[u][j]].begin();
            f[0][st[u]+son[u].size()]=1;
        }
        vector<int>ls;
        for(int x=1;x<=n;x++){
            for(int j=0;j<(int)son[x].size();j++){
                int c=son[x][j];ls.clear();
                if(adj[c].size()<=j+1){
                    int las=-1;
                    for(auto u:adj[c])if(c<u&&u<x){
                        int k=getk(x,u);
                        if(k!=las)ls.push_back(k),las=k;
                    }
                }else for(int k=0;k<=j;k++)ls.push_back(k);
                for(auto k:ls){
                    int L=son[x][k]+1,R=k==0?x-1:son[x][k-1];
                    L=max(L,c+1);if(L>R)continue;
                    int l=lower_bound(adj[c].begin(),adj[c].end(),L)-adj[c].begin();
                    int r=upper_bound(adj[c].begin(),adj[c].end(),R)-adj[c].begin();
                    if(l<r)qry.push_back({x,k,j,c,l,r});
                }
            }
        }
        cout<<n<<' ';int tms=m-1,cur=0;
        while(tms--){
            int nxt=cur^1;
            for(int u=1;u<=n;u++){
                int d=son[u].size(),now=0;
                for(int k=d;k>=0;k--){
                    int p=st[u]+k;
                    now+=f[cur][p];if(now>=mod)now-=mod;
                    f[nxt][p]=f[cur][p]+g[cur][p];if(f[nxt][p]>=mod)f[nxt][p]-=mod;
                    g[nxt][p]=g[cur][p]+g[cur][p];if(g[nxt][p]>=mod)g[nxt][p]-=mod;
                    if(k){
                        ok[est[u]+k-1]=now+h[cur][p-1];if(ok[est[u]+k-1]>=mod)ok[est[u]+k-1]-=mod;
                        h[nxt][p-1]=h[cur][p-1]+h[cur][p-1];if(h[nxt][p-1]>=mod)h[nxt][p-1]-=mod;
                        f[nxt][p]+=now;if(f[nxt][p]>=mod)f[nxt][p]-=mod;
                    }
                }
                sum[u]=now;
            }
            presum[0]=0;
            for(int u=1;u<=n;u++){
                presum[u]=presum[u-1]+sum[u];
                if(presum[u]>=mod)presum[u]-=mod;
            }
            for(int x=1;x<=n;x++){
                for(int k=0;k<=(int)son[x].size();k++){
                    int l=k==(int)son[x].size()?1:son[x][k]+1,r=k==0?x-1:son[x][k-1];
                    if(l<=r){
                        int v=presum[r]-presum[l-1];if(v<0)v+=mod;
                        f[nxt][st[x]+k]+=v;if(f[nxt][st[x]+k]>=mod)f[nxt][st[x]+k]-=mod;
                    }
                }
            }
            fill(val,val+atot,0);
            for(int u=1;u<=n;u++)for(int j=0;j<(int)son[u].size();j++)val[ast[son[u][j]]+pos[est[u]+j]]=ok[est[u]+j];
            for(int c=1;c<=n;c++){
                int now=0;
                for(int j=0;j<(int)adj[c].size();j++){
                    now+=val[ast[c]+j];if(now>=mod)now-=mod;
                    val[ast[c]+j]=now;
                }
            }
            for(auto [mx,cnt,p,id,l,r]:qry){
                int v=val[ast[id]+r-1];
                if(l)v-=val[ast[id]+l-1];
                if(v<0)v+=mod;
                g[nxt][st[mx]+cnt]+=v;if(g[nxt][st[mx]+cnt]>=mod)g[nxt][st[mx]+cnt]-=mod;
                h[nxt][st[mx]+p]+=v;if(h[nxt][st[mx]+p]>=mod)h[nxt][st[mx]+p]-=mod;
            }
            cur=nxt;int ans=0;
            for(int i=0;i<tot;i++){ans+=f[cur][i];if(ans>=mod)ans-=mod;}
            cout<<ans<<' ';
        }cout<<'\n';
    }
    return 0;
}

::::