SP7363_Tree_Sum题解

好题，话说我写黑题题解是不是有点飘了 www。

众所周知，第二类斯特林数有一个如下的性质：

$$m^n=\sum\limits_{i=0}^n \begin{Bmatrix} n \\ i \end{Bmatrix}\times i! \times \binom{m}{i}$$

更众所周知的是，杨辉三角递推式：

$$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$$

原题的答案求的是：

$$ans_{x}=\sum\limits_{i=1}^n (dis(x,i))^k$$

其中$ans_x$ 表示在以$x$ 为根节点的情况下的答案，注意到选取的$x$ 不同所对应的答案不同，这启示我们进行类似于换根 DP 的计算（是不是有点太超前了）。

我们利用上面的公式变换一下：

$$\begin{aligned} ans_{x} & =\sum\limits_{i=1}^n (dis(x,i))^k \\ & = \sum_{i=1}^n \sum_{j=0}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix}\times j! \times \binom{dis(x,i)}{j} \\ & = \sum_{j=0}^{k} \begin{Bmatrix} k \\ j \end{Bmatrix}\times j! \sum_{i=1}^n \binom{dis(x,i)}{j} \end{aligned}$$

注意到前面可以暴力处理，瓶颈在于后面，考虑如何快速求后面的式子。

我们不妨考虑树形 DP 和换根 DP 计算（还真是换根耶），设$f(i,j)$ 表示以$i$ 及其子树内，$\dbinom{dis(x,i)}{j}$ 的总和，考虑转移方程推导。

考虑转移，转移由孩子节点转移过来，而根节点求的为$\sum\limits_{v\in sub(u)} \binom{dis(u,v)}{j}$，转化为求$\sum\limits_{x\in son(u)} \sum\limits_{v\in sub(u)} \binom{dis(x,v)+1}{j}$，用上面提到的组合数递推式即可解得：

$$f(u,j)=\sum_{v\in son(u)} f(v,j)+f(v,j-1)$$

求解完之后考虑换根，我们不妨设为$g(i,j)$。换根的式子推导过于繁杂，这里篇幅限制，感兴趣可以看其他的题解，方程如下：

$$g(u,j)=g(fa,j)+g(fa,j-1)-2\times f(u,j-1)-f(u,j-2)$$

预处理斯特林数和阶乘即可，时间复杂度$O(nk+k^2)$。

多测太难受了啊：

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=5e4+15,MK=26,MOD=1e9+7;
int f[MN][MK],s[MK][MK],pw[MK],n,K;
vector<int> adj[MN];

void init(){
    pw[0]=1;
    for(int i=1;i<MK;i++) pw[i]=pw[i-1]*i%MOD;
    s[0][0]=1;
    for(int i=1;i<MK;i++){
        for(int j=1;j<=i;j++){
            s[i][j]=(s[i-1][j-1]+j*s[i-1][j]%MOD)%MOD;
        }
    }
}

void dfs1(int u,int pre){
    f[u][0]=f[u][1]=1;
    for(auto v:adj[u]){
        if(v==pre) continue;
        dfs1(v,u);
        f[u][0]=(f[u][0]+f[v][0])%MOD;
        for(int i=1;i<=K;i++){
            f[u][i]=(f[u][i]+f[v][i]+f[v][i-1])%MOD;
        }
    }
}

void dfs2(int u,int pre){
    if(pre){
        for(int i=K;i>=0;i--){
            f[u][i]=f[pre][i];
            if(i>0){
                f[u][i]=(f[u][i]+f[pre][i-1])%MOD;
                f[u][i]=(f[u][i]-f[u][i-1]*2+MOD)%MOD;
            }
            if(i>1) f[u][i]=(f[u][i]-f[u][i-2]+MOD)%MOD;
        }
    }
    for(auto v:adj[u]){
        if(v==pre) continue;
        dfs2(v,u);
    }
}

void clear(){
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) adj[i].clear();
}

void solve(){
    clear();
    cin>>n>>K;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        u++,v++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++){
        int ans=0;
        for(int j=0;j<=K;j++){
            ans=(ans+f[i][j]*pw[j]%MOD*s[K][j]%MOD)%MOD;
        }
        cout<<ans<<'\n';
    }
    cout<<'\n';
}

signed main(){
    ios::sync_with_stdio(0);
    init();
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}