传送门

题意：

给你k和一棵n个点的树，每个边边权为1，对每个点i求 ∑nj=1dis(i,j)k ∑ j = 1 n d i s ( i , j ) k

n≤50000 k≤150 n ≤ 50000   k ≤ 150

Solution:

首先有一个结论： xn=∑ni=1Cix∗Sin∗i! x n = ∑ i = 1 n C x i ∗ S n i ∗ i !

组合意义上的证明： xn x n 表示在x个不同的盒子里放n个不同的球

然后我们枚举放在几个盒子里， Cix C x i 表示在x个盒子里选i个要放球的盒子， Sin S n i 表示把这n个球分配到这i个不同的盒子， i! i ! 表示这i个盒子选的顺序

然后我们转换一下式子：

∑nj=1dis(i,j)k=∑nj=1∑kl=1Slk∗l!∗C(dis(i,j),l)=∑kl=1Slk∗l!∑nj=1C(dis(i,j),l) ∑ j = 1 n d i s ( i , j ) k = ∑ j = 1 n ∑ l = 1 k S k l ∗ l ! ∗ C ( d i s ( i , j ) , l ) = ∑ l = 1 k S k l ∗ l ! ∑ j = 1 n C ( d i s ( i , j ) , l )

那么我们只需要求出后面的那些 ∑nj=1C(dis(i,j),l) ∑ j = 1 n C ( d i s ( i , j ) , l ) 就好了

这个过程可以依据组合数的递推式，通过树形DP来实现

fd[x][l] f d [ x ] [ l ] 表示 的子树∑i∈x的子树C(dis(x,i),l) 的 子 树 ∑ i ∈ x 的 子 树 C ( d i s ( x , i ) , l )

fu[x][l] f u [ x ] [ l ] 表示 的子树∑i∉x的子树C(dis(x,i),l) 的 子 树 ∑ i ∉ x 的 子 树 C ( d i s ( x , i ) , l )

转移即为：

fd[x][l]=∑y∈sonxfd[y][l]+fd[y][l−1] f d [ x ] [ l ] = ∑ y ∈ s o n x f d [ y ] [ l ] + f d [ y ] [ l − 1 ]

fu[x][l]+=fu[fa][l]+fu[fa][l−1] f u [ x ] [ l ] + = f u [ f a ] [ l ] + f u [ f a ] [ l − 1 ]

fu[x][l]+=fd[fa][l]+fd[fa][l−1] f u [ x ] [ l ] + = f d [ f a ] [ l ] + f d [ f a ] [ l − 1 ]

fu[x][l]−=fd[x][l]+fd[x][l−1] f u [ x ] [ l ] − = f d [ x ] [ l ] + f d [ x ] [ l − 1 ]

fu[x][l]−=fd[x][l−1]+fd[x][l−2] f u [ x ] [ l ] − = f d [ x ] [ l − 1 ] + f d [ x ] [ l − 2 ]

转移类似容斥

代码：

#include<cstdio>
#include<iostream>
using namespace std;
int n,k,head[50010];
const int mod=10007;
struct edg{
    int to,next;
}e[100010];
int S[200][200],mi[200]; 
int size,fd[50010][160],fu[50010][160];
void add(int x,int y){size++;e[size]={
  y,head[x]};head[x]=size;}
void dfs1(int x,int fa)
{
    fd[x][0]=1;
    for (int i=head[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if (y==fa) continue;
        dfs1(y,x);
        for (int j=0;j<=k;j++)
        {
            if (j)
                fd[x][j]=(fd[x][j]+fd[y][j]+fd[y][j-1])%mod;
            else fd[x][j]=(fd[x][j]+fd[y][j])%mod;
        }
    }
}
void dfs2(int x,int fa)
{
    if (fa)
    {
        for (int i=0;i<=k;i++)
        {
            if (i)
            {
                fu[x][i]=(fu[x][i]+fu[fa][i]+fu[fa][i-1])%mod;
                fu[x][i]=(fu[x][i]+fd[fa][i]+fd[fa][i-1])%mod;
                fu[x][i]=(fu[x][i]-(fd[x][i]+fd[x][i-1])%mod+mod)%mod;
                fu[x][i]=(fu[x][i]-fd[x][i-1]+mod)%mod;
                if (i>1) fu[x][i]=(fu[x][i]-fd[x][i-2]+mod)%mod;
            }
            else fu[x][0]=n-fd[x][0];
        }
    }
    for (int i=head[x];i;i=e[i].next)
    {
        int y=e[i].to;
        if (y==fa) continue;
        dfs2(y,x);
    }
}
int main()
{
    int L,now,A,B,Q;
    scanf("%d%d%d%d%d%d%d",&n,&k,&L,&now,&A,&B,&Q);
    for (int i=1;i<n;i++){
        now=(now*A+B)%Q;
        int tmp=i<L?i:L;
        int x=i-now%tmp,y=i+1;
        add(x,y);add(y,x);
    }
    //scanf("%d%d",&n,&k);
    mi[0]=1;for (int i=1;i<=k;i++) mi[i]=mi[i-1]*i%mod;
    S[0][0]=1;
    for (int i=1;i<=k;i++)
        for (int j=1;j<=i;j++)
            S[i][j]=(S[i-1][j-1]+j*S[i-1][j])%mod;
    //for (int x,y,i=1;i<n;i++)
    //  scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs1(1,0);dfs2(1,0);
    for (int i=1;i<=n;i++)
    {
        int ans=0;
        for (int j=1;j<=k;j++)
            ans=(ans+1ll*S[k][j]*mi[j]*(fd[i][j]+fu[i][j]))%mod;
        printf("%d\n",ans);
    }
}