正題

題目鏈接:https://www.luogu.com.cn/problem/P4827

---

題目大意

一顆$n$個點的樹，定義$dis(i,j)$表示樹上$i,j$兩點的距離，對于每個$i$求$$\sum _{j=1}^{n}dis(i,j{)}^m$$

---

解題思路

根據斯特林數的性質我們有
$$n^m=\sum _{k=0}^m\left\{\begin{array}{c}m\\ k\end{array}\right\}\left(\genfrac{}{}{0ex}{}{n}{k}\right)k!$$
那么就有
$$dis(i,j{)}^m=\sum _{k=0}^m\left\{\begin{array}{c}m\\ k\end{array}\right\}(\genfrac{}{}{0ex}{}{dis(i,j)}{k})k!$$
也就是要求
$$\sum _{j=1}^{n}dis(i,j{)}^m=\sum _{j=1}^n(\sum _{k=0}^m\left\{\begin{array}{c}m\\ k\end{array}\right\}\left(\genfrac{}{}{0ex}{}{dis(i,j)}{k}\right)k!)$$
$$?\sum _{j=1}^{n}dis(i,j{)}^m=\sum _{k=0}^m\left\{\begin{array}{c}m\\ k\end{array}\right\}k!\sum _{j=1}^n(\genfrac{}{}{0ex}{}{dis(i,j)}{k})$$

考慮樹形$dp$計算后面的貢獻，設$f_{x,j}$表示以$1$為根，在$x$的子樹中在$\left(\genfrac{}{}{0ex}{}{di{s}_{1,y}}{j}\right)$的值和。可以根據$\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\left(\genfrac{}{}{0ex}{}{n?1}{m?1}\right)+\left(\genfrac{}{}{0ex}{}{n?1}{m}\right)$可以$O(nk)$求出

然后根據轉移方程換根求其他點為根的答案。

時間復雜度$O(nk)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=5e4+10,K=170,XJQ=10007; struct node{int to,next; }a[N*2]; int n,m,tot,S[N][K],fac[K]; int f[N][K],g[N][K],ls[N]; void init(){S[0][0]=S[1][1]=fac[0]=1;for(int i=1;i<=m;i++)fac[i]=fac[i-1]*i%XJQ;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)(S[i][j]=S[i-1][j-1]+j*S[i-1][j]%XJQ)%=XJQ;return; } void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x,int fa){f[x][0]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;dfs(y,x);for(int j=1;j<=m;j++)(f[x][j]+=f[y][j]+f[y][j-1])%=XJQ;(f[x][0]+=f[y][0])%=XJQ;}return; } int k(int x,int j,int fa) {return (g[fa][j]-f[x][j]-(j?f[x][j-1]:0)+2*XJQ)%XJQ;} void dp(int x,int fa){for(int j=1;j<=m;j++)g[x][j]=(k(x,j,fa)+k(x,j-1,fa))%XJQ;g[x][0]=k(x,0,fa)+1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;for(int j=1;j<=m;j++)(g[x][j]+=f[y][j]+f[y][j-1])%=XJQ;(g[x][0]+=f[y][0])%=XJQ;}for(int i=ls[x];i;i=a[i].next)if(a[i].to!=fa)dp(a[i].to,x);return; } int main() {scanf("%d%d",&n,&m);init();for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}dfs(1,1);for(int i=0;i<=m;i++)g[1][i]=f[1][i];for(int i=ls[1];i;i=a[i].next)dp(a[i].to,1);for(int i=1;i<=n;i++){int ans=0;for(int j=0;j<=m;j++)(ans+=S[m][j]*fac[j]%XJQ*g[i][j]%XJQ)%=XJQ;printf("%d\n",ans);} }

總結

以上是生活随笔為你收集整理的P4827-[国家集训队]Crash 的文明世界【树形dp,换根法,斯特林数】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。