洛谷 P4827 [国家集训队] Crash 的文明世界

「爱情、让人受尽委屈。」 2021-11-23 15:52 352阅读 0赞

### 题目描述 ###

给你一棵 n 个点的树，对于树上的每个节点 i，求 \\(\\sum\_\{j=1\}^ndis(i,j)^k\\)。其中 \\(dis(i,j)\\) 为两点在树上的距离。

### 输入格式 ###

第一行两个整数 n,k。

接下来 n-1 行，每行两个整数 (x,y)，表示一条树边。

### 输出格式 ###

一行一个整数，表示答案对 10007 取模的值。

### 样例输入 ###

5 2
    1 2
    1 3
    2 4
    2 5

### 样例输出 ###

10
    7
    23
    18
    18

### 数据范围 ###

对于 \\(30\\%\\) 的数据，\\(n\\le5000,k\\le50\\)

对于另 \\(20\\%\\) 的数据，保证树是一条链

对于所有数据，\\(n\\le50000,k\\le150\\)

## 解析 ##

题目要求的值即为\\(\\sum\_\{i=1\}^\{n\}dis(x,i)^k\\)。形式上可以用第二类斯特林数的性质进行化简。  
\\\[ \\begin\{align\} Ans &= \\sum\_\{i=1\}^\{n\}dis(x,i)^k \\\\ &= \\sum\_\{i=1\}^\{n\} \\sum\_\{j=0\}^\{k\} S(k,j)\*j!\*C\_\{dis(x,i)\}^\{j\}\\\\ &= \\sum\_\{j=0\}^\{k\}S(k,j)\*j!\*\\sum\_\{i=1\}^\{n\}(C\_\{dis(x,i)-1\}^\{j\}+C\_\{dis(x,i)-1\}^\{j-1\})\\\\ \\end\{align\} \\\]  
其中斯特林数和阶乘都是可以预处理的。接下来的问题是如何求\\(\\sum\_\{i=1\}^\{n\}C\_\{dis(x,i)\}^\{j\}\\)。

设\\(f\[i\]\[j\]\\)表示对于第i个点的子树中上式的值，则\\(C\_\{dis(x,i)-1\}^\{j\}\\)的值可以看做是在i点儿子的f中并由儿子推出\\(f\[i\]\[j\]\\)的值。那么我们可以先假设1号点为根节点，用一遍dfs求出f的值，状态转移方程为  
\\\[ f\[i\]\[j\]=\\sum\_\{son\}f\[son\]\[j\]+f\[son\]\[j-1\] \\\]  
然后用换根DP求出以任意i点作为根节点时的\\(f\[i\]\[j\]\\)即可。最后的答案为  
\\\[ \\sum\_\{j=0\}^\{k\}S(k,j)\*j!\*f\[i\]\[j\] \\\]  
动态规划时注意边界条件。

## 代码 ##

#include <iostream> #include <cstdio> #define N 50002 #define K 201 #define int long long using namespace std; const int mod=10007; int head[N],ver[N*2],nxt[N*2],l; int n,k,i,j,f1[N][K],f2[N][K],g[K],f[K],s[K][K]; void insert(int x,int y) { l++; ver[l]=y; nxt[l]=head[x]; head[x]=l; } void dfs1(int x,int pre) { f1[x][0]=1; for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(y!=pre){ dfs1(y,x); for(int j=1;j<=k;j++) f1[x][j]=(f1[x][j]+f1[y][j]+f1[y][j-1])%mod; f1[x][0]=(f1[x][0]+f1[y][0])%mod; } } } void dfs2(int x,int pre) { for(int i=0;i<=k;i++) f2[x][i]=f1[x][i]; if(pre){ for(int i=1;i<=k;i++) g[i]=(f2[pre][i]-f1[x][i]+mod-f1[x][i-1]+mod)%mod; g[0]=(f2[pre][0]-f1[x][0]+mod)%mod; for(int i=1;i<=k;i++) f2[x][i]=(f2[x][i]+g[i]+g[i-1])%mod; f2[x][0]=(f2[x][0]+g[0])%mod; } for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(y!=pre) dfs2(y,x); } } signed main() { freopen("C.in","r",stdin); freopen("C.out","w",stdout); cin>>n>>k; for(i=1;i<n;i++){ int u,v; cin>>u>>v; insert(u,v); insert(v,u); } s[0][0]=s[1][1]=1; f[0]=1; for(i=1;i<=k;i++){ for(j=1;j<=k;j++) s[i][j]=(s[i-1][j-1]+j*s[i-1][j])%mod; } for(i=1;i<=k;i++) f[i]=f[i-1]*i%mod; dfs1(1,0); dfs2(1,0); for(i=1;i<=n;i++){ int ans=0; for(j=0;j<=k;j++) ans=(ans+(s[k][j]*f[j]%mod*f2[i][j])%mod)%mod; cout<<ans<<endl; } fclose(stdin); fclose(stdout); return 0; }

转载于:https://www.cnblogs.com/LSlzf/p/11178684.html