网站怎么免费做推广方案,网站恶意点击,东平网站制作哪家好,淘宝客怎么自己做网站小 L 出了一道题#xff1a; 给定一棵 n n n 个点的树#xff0c;定义两点之间的距离为连接两点的唯一简单路径的边的条数。求树上的点两两之间的距离之和。 小 Q 觉得这题太简单了#xff0c;于是给它加强了一下#xff1a; 给定一棵 n n n 个点的树#xff0c;求树上的…小 L 出了一道题 给定一棵 n n n 个点的树定义两点之间的距离为连接两点的唯一简单路径的边的条数。求树上的点两两之间的距离之和。 小 Q 觉得这题太简单了于是给它加强了一下 给定一棵 n n n 个点的树求树上的点两两之间的距离的 k k k 次方之和。 这下他们都不会做了你能帮帮他们吗 几个记号 T ( n ) T(n) T(n) 表示子树 n n n f a i fa_i fai 表示 i i i 的父亲 dis ( i , j ) \operatorname{dis}(i,j) dis(i,j) 表示树上两点 i , j i,j i,j 的距离 s o n i son_i soni 表示 i i i 的儿子。
将 x k x^k xk 斯特林展开得到 x k ∑ i 0 x { k i } ⋅ i ! ⋅ ( x i ) x^k\sum\limits_{i0}^x{k\brace i}\cdot i!\cdot\binom xi xki0∑x{ik}⋅i!⋅(ix)
其中 { k i } {k\brace i} {ik} 是第二类斯特林数表示把 k k k 个数划分成 i i i 个无序非空集合的方案数。
从组合意义上可以说明式子成立 x k x^k xk 表示把 k k k 个不同的球放入 x x x 个不同盒子最后盒子可以为空的方案数。有 ( x i ) \binom xi (ix) 种方案选择 i i i 个盒子放球其他盒子为空。然后 { k i } k\brace i {ik} 就是把 k k k 个球分给 i i i 个相同盒子的方案数。因为盒子是不同的所以还要乘上 i ! i! i!。式子显然成立。
在题目中只需枚举到 k k k 即可因为若 k i ki ki 斯特林数就为 0 0 0
而题目是要求 ∑ i 1 n ∑ j i 1 n ∑ l 0 k { k l } ⋅ l ! ⋅ ( dis ( i , j ) l ) ∑ l 0 k { k l } ⋅ l ! ( ∑ i 1 n ∑ j i 1 n ( dis ( i , j ) l ) ) \sum\limits_{i1}^n\sum\limits_{ji1}^n\sum\limits_{l0}^k{k\brace l}\cdot l!\cdot\binom{\operatorname{dis}(i,j)}l\sum\limits_{l0}^k{k\brace l}\cdot l!\left(\sum\limits_{i1}^n\sum\limits_{ji1}^n\binom{\operatorname{dis}(i,j)}l\right) i1∑nji1∑nl0∑k{lk}⋅l!⋅(ldis(i,j))l0∑k{lk}⋅l!(i1∑nji1∑n(ldis(i,j)))
问题转换为对于每个 l ∈ [ 1 , k ] l\in[1,k] l∈[1,k]
求 ∑ i 1 n ∑ j i 1 n ( dis ( i , j ) l ) \sum\limits_{i1}^n\sum\limits_{ji1}^n\binom{\operatorname{dis}(i,j)}l i1∑nji1∑n(ldis(i,j))。
设 f i , j f_{i,j} fi,j 表示 ∑ x ∈ T ( i ) ( d i s ( f a i , x ) j ) \sum\limits_{x\in T(i)}\binom{\operatorname{dis(fa_i,x)}}{j} x∈T(i)∑(jdis(fai,x))就是 ( i 子树的所有点到 f a i 距离 j ) \binom{i 子树的所有点到 fa_i 距离}{j} (ji子树的所有点到fai距离) 之和。
考虑如何转移。由于有 ( x 1 j ) ( x j ) ( x j − 1 ) \binom{x1}{j}\binom{x}{j}\binom{x}{j-1} (jx1)(jx)(j−1x)所以 f i , j ∑ x ∈ s o n i ( f x , j f x , j − 1 ) f_{i,j}\sum\limits_{x\in son_i}(f_{x,j}f_{x,j-1}) fi,jx∈soni∑(fx,jfx,j−1)。
在计算答案时要将每个 i i i 的子树进行“合并”。由于 ( x y j ) ∑ i 0 j ( x j ) ( y i − j ) \binom{xy}{j}\sum\limits_{i0}^j\binom{x}{j}\binom{y}{i-j} (jxy)i0∑j(jx)(i−jy)所以对于每个 j j j 答案要加上 ∑ l 0 j f x , l f y , j − l \sum\limits_{l0}^jf_{x,l}f_{y,j-l} l0∑jfx,lfy,j−l。这里可以用前缀和优化。时间复杂度 O ( n k 2 ) O(nk^2) O(nk2) O ( n k 2 ) O(nk^2) O(nk2) 实际上是过不了的所以我们要发扬人类智慧。如果是一条链由于儿子只有一个显然不可能有“合并”就不用算了如果所有的 x ∈ T ( i ) x\in{T(i)} x∈T(i)都有 dis ( f a i , x ) j \operatorname{dis}(fa_i,x)j dis(fai,x)j就说明 f i , k f_{i,k} fi,k 为 0 0 0可以少枚举。通过一系列操作成功水过。
代码如下
#includebits/stdc.h
using namespace std;
typedef long long ll;
const ll mod998244353;
const int N1e61,INF1e9;
int n,k,fa[N],b[N],sz[N];
int head[N],nxt[N1],to[N1],cnt,dep[N],maxdep[N];
ll ans[101],Ans,stl[101][101],f[101],inv[101],dp[N][101];
void add(int u,int v)
{to[cnt]v;nxt[cnt]head[u];head[u]cnt;
}
ll ksm(ll a,ll b)
{ll ans1;while(b){if(b1) ansans*a%mod;b1;aa*a%mod;}return ans;
}
ll C(ll x,ll y)
{ll sum1;for(int i1;iy;i){sumsum*(x-i1)%mod;}return (sum*inv[y]%modmod)%mod;
}
void dfs(int u,int fa)
{dep[u]dep[fa]1;maxdep[u]dep[u];for(int ihead[u];i;inxt[i]) if(to[i]!fa) dfs(to[i],u),maxdep[u]max(maxdep[u],maxdep[to[i]]);
}
void solve(int u,int fa)
{int sz0;for(int ihead[u];i;inxt[i]){if(to[i]!fa){sz;solve(to[i],u);if(sz1){for(int l0;lmin(k,maxdep[u]*2-2*dep[u]);l){for(int p0;pl;p)ans[l](ans[l]1ll*dp[u][p]*dp[to[i]][l-p])%mod;}}for(int l0;lk;l) ans[l](ans[l]dp[to[i]][l])%mod;for(int j0;jk;j) (dp[u][j]dp[to[i]][j])%mod;}}dp[u][0];for(int j1;jk;j){for(int ihead[u];i;inxt[i]){if(to[i]fa) continue;(dp[u][j]dp[to[i]][j-1])%mod;}if(j1) dp[u][j];dp[u][j]%mod;}
}
void init()
{stl[0][0]1;for(int i1;ik;i){for(int j1;ji;j){stl[i][j](stl[i-1][j-1]stl[i-1][j]*j)%mod;}}f[0]1;for(int i1;ik;i) f[i]f[i-1]*i%mod;inv[k]ksm(f[k],mod-2);for(int ik-1;i0;i--) inv[i]inv[i1]*(i1)%mod;
}
int read()
{int sum0,cgetchar();while(c48||c57) cgetchar();while(c48c57) sumsum*10c-48,cgetchar();return sum;
}
int main()
{nread(),kread();init();for(int i1,x,y;in;i){xread(),yread();add(x,y),add(y,x);}dfs(1,0);solve(1,0);for(int i0;ik;i) Ans(Ansstl[k][i]*f[i]%mod*ans[i])%mod;printf(%lld,Ans);
}
