题解：P16905 [CCO 2026] Tree Traversals

· · 题解

先考虑所有同层转移，同层之间最浅的祖先是必然被走到的，因此可以得到 k 的最小值 K。那么不同层间转移的距离不超过 K+1。

我们对每个点维护 f(i,0/1) 表示路径走完第 dp_i 层停在 i 是否钦定 k>K 的方案数，同层起点到终点转移对所有 f 求和减去自己的然后一个阶乘就做完了，考虑走到下一层，二分 BFS 序下一层中当前点可以以不超过 K 走到的范围，转移形如区间加，差分一下就可以了。

实现地不太牛，O(n\log^2n)，不过容易优化掉 \log。

const int N=5e5+5,T=20;

int n,q;
vec<int> g[N];
mint ans[N];
int dp[N],bcnt,bfn[N],nfb[N];
int Q[N],hd,tl,fa[N],DP,lb[N],rb[N];
int FA[T][N];
il int up(int x,int k){per(t,T-1,0)if(k>=(1<<t))k-=1<<t,x=FA[t][x];return x;}
il int lca(int x,int y){
    if(dp[x]>dp[y])swap(x,y);
    per(t,T-1,0)if(dp[FA[t][y]]>=dp[x])y=FA[t][y];
    if(x==y)return x;
    per(t,T-1,0)if(FA[t][x]!=FA[t][y])x=FA[t][x],y=FA[t][y];
    return FA[0][x];
}
il int dis(int x,int y){return dp[x]+dp[y]-2*dp[lca(x,y)];}
int lk,ls[N],rs[N];
mint f[N][2],fc[N];

void INIT(){
    n=5e5;fc[0]=1;rep(i,1,n)fc[i]=fc[i-1]*i;
}
void MAIN(){
    read(n,q);
    rep(i,1,n)g[i].clear();
    rep(i,2,n){int x,y;read(x,y),g[x].pub(y),g[y].pub(x);}
    rep(i,1,n)ans[i]=0;
    bcnt=0;
    Q[hd=tl=1]=1;DP=0;
    while(hd<=tl){
        int x=Q[hd++];
        nfb[bfn[x]=++bcnt]=x;dp[x]=dp[fa[x]]+1;
        if(DP<dp[x])lb[DP=dp[x]]=bcnt;rb[dp[x]]=bcnt;
        for(auto y:g[x])if(y!=fa[x])fa[y]=x,Q[++tl]=y;
    }
    repl(d,1,DP){
        int lst=lb[d+1]-1;
        rep(i,lb[d],rb[d]){
            int x=nfb[i];
            int LS=inf,RS=-inf;
            for(auto y:g[x])if(y!=fa[x])chmin(LS,bfn[y]),chmax(RS,bfn[y]);
            if(LS<=RS)ls[x]=LS,rs[x]=RS;else ls[x]=lst+1,rs[x]=lst;
            lst=rs[x];
        }
    }
    rep(i,1,n)FA[0][i]=fa[i];repl(t,1,T)rep(i,1,n)FA[t][i]=FA[t-1][FA[t-1][i]];
    lk=0;
    rep(d,1,DP)chmax(lk,dis(nfb[lb[d]],nfb[rb[d]]));
    rep(i,1,n)f[i][0]=f[i][1]=0;
    f[1][0]=1;
    rep(d,1,DP){
        mint sum[2];rep(i,lb[d],rb[d])rep(j,0,1)sum[j]+=f[i][j];
        if(lb[d]<rb[d])rep(i,lb[d],rb[d])rep(j,0,1)f[i][j]=(sum[j]-f[i][j])*fc[rb[d]-lb[d]-1];
        if(d==DP)break;
        rep(i,lb[d],rb[d]){
            int x=nfb[i];
            int LB=[&]()->int {
                int l=lb[d+1],r=rs[x]+1;
                while(l<r){
                    int m=l+r>>1;
                    if(dis(x,nfb[m])<=lk)r=m;
                    else l=m+1;
                }return l;
            }(),RB=[&]()->int {
                int l=ls[x]-1,r=rb[d+1];
                while(l<r){
                    int m=l+r+1>>1;
                    if(dis(x,nfb[m])<=lk)l=m;
                    else r=m-1;
                }return l;
            }();
            f[lb[d+1]][1]+=f[i][1];
            if(LB<=RB){
                f[LB][0]+=f[i][0],f[lb[d+1]][1]+=f[i][0],f[LB][1]-=f[i][0];
                if(RB+1<=rb[d+1])f[RB+1][0]-=f[i][0],f[RB+1][1]+=f[i][0];
            }else f[lb[d+1]][1]+=f[i][0];
        }
        rep(i,lb[d+1]+1,rb[d+1])f[i][0]+=f[i-1][0],f[i][1]+=f[i-1][1];
    }
    ans[lk]=ans[lk+1]=0;rep(i,lb[DP],rb[DP])ans[lk]+=f[i][0],ans[lk+1]+=f[i][1]+f[i][0];
    rep(i,lk+2,n)ans[i]=ans[i-1];
    rep(i,1,q){
        int k;read(k);
        put(ans[k],0);
    }put("");
}