Tag

第二类斯特林数，dp

题目链接

题意

给定一棵 n 点的树，定义 $dis(u,v)$ 为树上路径长度。对于每个点，定义 $E_u=\sum_{v=1}^n dis(u,v)^k$ ，其中 k 为给定数。

求每个 $E_i\mod 10007 (i=1\sim n)$ .

思路

求幂可以考虑转化成第二类斯特林数。有公式： $x^n = \sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} x^{\underline{k}}.$

从而 $E_u = \sum_{v=1}^n (dis(u, v))^k = \sum_{i=0}^k \begin{Bmatrix} k \\ i \end{Bmatrix} \sum_{v=1}^n (dis(u, v))^{\underline{i}}.$

令 $f[u][k] = \sum_{v \in T_u} (dis(u, v))^{\underline{k}},$ $T_u$ 为 $u$ 为根的子树，且显然有 $(x+1)^{\underline{k}} = x^{\underline{k}}+kx^{\underline{k-1}}$

考虑求 $f[u][k].$
$$ f[u][k]=\sum_{v\in T_u} dis(u,v)^{\underline{k}} =\sum_{v\in son(u)}\sum_{w\in T_v}[dis(v,w)+1]^{\underline{k}} $$
这时候就可以运用上述公式。
$$ f[u][k]=\sum_{v\in son(u)}\sum_{w\in T_v} [dis(v,w)^{\underline{k}}+k\times dis(v,w)^{\underline{k-1}}] $$
回到 $f[u][k]$ 的定义，可得到转移方程
$$ f[u][k]=\sum_{v\in son(u)} f[v][k]+k\times f[v][k-1] $$
两遍 DFS 即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10,K=510,mod=10007;
int n,k,S[N][K],f[N][K],g[N][K];
vector<int> v[N];

void dfs1( int x,int fa )
{
        f[x][0]=1; 
        for ( int i=1; i<=k; i++ ) f[x][i]=0;
        for ( auto y : v[x] )
        {
                if ( y==fa ) continue;
                dfs1( y,x );
                f[x][0]=(f[x][0]+f[y][0])%mod;
                for ( int i=1; i<=k; i++ )
                        f[x][i]=( f[x][i]+(f[y][i]+i*f[y][i-1]))%mod;
        }
}

void dfs2( int x,int fa )
{
        if ( !fa ) for ( int i=0; i<=k; i++ ) g[x][i]=f[x][i];
        for ( auto y : v[x] )
        {
                if ( y==fa ) continue;
                g[y][0]=g[x][0];
                for ( int i=1; i<=k; i++ )
                {
                        int t1=(g[x][i]-(f[y][i]+i*f[y][i-1]))%mod;
                        int t2=( g[x][i-1]-( f[y][i-1]+(i-1)*(i-2>=0 ? f[y][i-2] : 0) ))%mod;
                        g[y][i]=( f[y][i]+( t1+i*t2) )%mod;
                }
                dfs2( y,x );
        }
}

void init()
{
        S[0][0]=1;
        for ( int i=1; i<=500; i++ )
         for ( int j=1; j<=i; j++ )
                S[i][j]=(S[i-1][j-1]+S[i-1][j]*j)%mod;
}

int main()
{
        int T; scanf( "%d",&T ); init();
        while ( T-- )
        {
                scanf( "%d%d",&n,&k );
                for ( int i=1; i<=n; i++ )
                        v[i].clear();
                for ( int i=1,x,y; i<n; i++ )
                        scanf( "%d%d",&x,&y ),v[x].push_back(y),v[y].push_back(x);

                dfs1( 1,0 ); dfs2( 1,0 );

                for ( int x=1;x<=n; x++ )
                {
                        int res=0;
                        for ( int i=0; i<=k; i++ )
                                res=( res+S[k][i]*g[x][i])%mod;
                        printf( "%d\n",(res+mod)%mod );
                }
        }
}