HDU - 4625 JZPTREE（第二类斯特林数+树DP）

时间：2023-03-09 07:34:21
HDU - 4625 JZPTREE（第二类斯特林数+树DP）

https://vjudge.net/problem/HDU-4625

题意

给出一颗树，边权为1，对于每个结点u，求sigma（dist（u，v）^k）。

分析

贴个官方题解

HDU - 4625 JZPTREE（第二类斯特林数+树DP）

n^k并不好转移，于是用第二类斯特林数转化一下，这样可以预处理第二类斯特林数，而sigma（C(dist(u,v),i)）则利用C(n,x)=C(n-1,x)+C(n-1,x-1)来进行树DP转移得到。

设dp[u][k]=sigma（C(dist(u,v),k)）,则dp[u][k]=dp[v][k]+dp[v][k-1]，这里v是u的儿子。先dfs一次算dp值。

接下来再dfs一次，每次以u为根，计算Eu，注意转移时需要将子结点作为新的根，此时需要计算一下合适的dp值。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <cmath>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <stack>

#include <set>

#include <bitset>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define ms(a, b) memset(a, b, sizeof(a))

#define pb push_back

#define mp make_pair

#define pii pair<int, int>

#define IOS ios::sync_with_stdio(0);cin.tie(0);

#define random(a, b) rand()*rand()%(b-a+1)+a

#define pi acos(-1.0)

const ll INF = 0x3f3f3f3f3f3f3f3fll;

const int inf = 0x3f3f3f3f;

const int maxn = 5e4+;

const int maxm = 1e5+;

const int mod = ;

struct edge{

    int t,n;

    edge(int t=,int n=):

        t(t),n(n){}

}e[maxn<<];

int head[maxn],tot;

void addedge(int u,int v){

    e[++tot]=edge(v,head[u]),head[u]=tot;

    e[++tot]=edge(u,head[v]),head[v]=tot;

}

int n,k;

int s[][],fac[];

void init(){

    s[][]=fac[]=;

    for(int i=;i<;i++){

        fac[i]=fac[i-]*i%mod;

        for(int j=;j<;j++){

            s[i][j]=(j*s[i-][j]+s[i-][j-])%mod;

        }

    }

    for(int i=;i<;i++)

        for(int j=;j<;j++)

            s[i][j]=s[i][j]*fac[j]%mod;

}

int dp[maxn][];

void pre_dfs(int u,int p){

    dp[u][]=;

    for(int i=;i<=k;i++) dp[u][i]=;

    for(int i=head[u];~i;i=e[i].n){

        int v = e[i].t;

        if(v!=p){

            pre_dfs(v,u);

            for(int j=;j<=k;j++){

                dp[u][j]+=dp[v][j];

                if(j) dp[u][j]+=dp[v][j-];

                dp[u][j]%=mod;

            }

        }

    }

}

int ans[maxn];

void dfs(int u,int p){

    ans[u]=;

    for(int i=;i<=k;i++) ans[u]=(ans[u]+s[k][i]*dp[u][i])%mod;

    for(int i=head[u];~i;i=e[i].n){

        int v=e[i].t;

        if(v!=p){

            for(int j=;j<=k;j++){

                dp[u][j]+=mod-dp[v][j];

                if(j) dp[u][j]+=mod-dp[v][j-];

                dp[u][j]%=mod;

            }

            for(int j=;j<=k;j++){

                dp[v][j]+=dp[u][j];

                if(j) dp[v][j]+=dp[u][j-];

                dp[v][j]%=mod;

            }

            dfs(v,u);

            for(int j=;j<=k;j++){

                dp[v][j]+=mod-dp[u][j];

                if(j) dp[v][j]+=mod-dp[u][j-];

                dp[v][j]%=mod;

            }

            for(int j=;j<=k;j++){

                dp[u][j]+=dp[v][j];

                if(j) dp[u][j]+=dp[v][j-];

                dp[u][j]%=mod;

            }

        }

    }

}

int main(){

#ifdef LOCAL

    freopen("in.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

#endif

    int t;

    scanf("%d",&t);

    init();

    while(t--){

        tot=;

        memset(head,-,sizeof head);

        int u,v;

        scanf("%d%d",&n,&k);

        for(int i=;i<n;i++){

            scanf("%d%d",&u,&v);

            addedge(u,v);

        }

        pre_dfs(,-);

        dfs(,-);

        for(int i=;i<=n;i++) printf("%d\n",ans[i]);

    }

    return ;

}

相关文章