银联高校极客挑战赛-复赛-D-多项式
银联高校极客挑战赛-复赛-D-多项式
$f[u][j]$表示以$u$为根的子树中$u$到所有$v$(子树中的节点)的路径和的$j$次方的和。 可以得到一个动态转移方程: 考虑二项式展开: $(a+b+c)^j = \sum_{k = 0}^j C(j, k) (a+b)^k c^{j-k}$
类似的: $(a+b+c)^j + (d+e+c)^j= \sum_{k = 0}^j C(j, k) ((a+b)^k + (d+e)^k) c^{j-k}$
所以通过这个性质可以得到动态转移方程: 记$fa[v]$表示节点$v$的父亲结点.$w$表示$(u, v)$之间的权值
$$f[u][j] = \sum_{fa[v]==u} \sum_{k=0}^jC(j, k) f[v][k] w^{j-k}$$
得到了从结点$u$到它的子树的结点的路径$K$次方权值和之后,我们还需要计算从结点$u$到它除去它的子树的结点也就是它的父亲的那边的那些结点的路径$K$次方权值和。
$g[v][j]$表示从结点v到除去结点$v$的子树中的结点(也就是$v$到$v$的父亲结点那个方向的结点)边权的$j$次方的和
记$v$结点的父亲结点是$u$.
记$u$和$v$之间的边权是$w$
所以我们可以得到动态转移方程.
$$t[j] = g[u][j] + f[u][j] - \sum_{k=0}^jC(j, k) f[v][k] w^{j-k}$$
$$g[v][j] = \sum_{k = 0}^j C(j, k) w ^ k t[j-k]$$
(备注:关于这个动态转移方程的解释如下)
$g[u][j]$表示从结点$u$到父亲结点方向的$j$次方权值和.
$f[u][j]$表示从结点$u$到它的子树方向结点的$j$次方权值和.
现在$v$是$u$的一个孩子结点.
那么通过我们计算得到的上面式子的$t$就是从结点$u$出发到除去$v$为根的子树的结点(包括$v$)的所有结点的$j$次方权值和.我们现在要算从$v$出发到除去自己子树下面的结点的$j$次方权值和.再加上$u$到$v$之间的权值的$j$次方即可
所以最后答案显然是:
$$ \frac{\sum_{i = 1}^n f[i][K] + g[i][K]}{n^2} $$
当然计算过程中要进行取模运算，以及最后的要进行模逆元的运算。
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cout << #x"=" << x << endl;
#define SZ(x) (x).size()
typedef long long LL;
const LL MOD = 998244353;
const int MAX_N = 1e5+100;
const int MAX_K = 15;
int n,K;
LL f[MAX_N][MAX_K], g[MAX_N][MAX_K];
LL ans;
struct P{
int v;
LL w;
};
vector<P> G[MAX_N];
int fa[MAX_N];
LL C[MAX_K][MAX_K];
LL W[MAX_K], h[MAX_K], t[MAX_K];
LL powN(LL base, LL n){
LL res = 1;
while(n){
if(n&1) res = res * base % MOD;
base = base * base % MOD;
n >>= 1;
}
return res;
}
LL inv(LL x){
return powN(x, MOD-2);
}
void add(LL &x, LL y){
x += y;
if(x >= MOD) x -= MOD;
}
// 计算f[u][j]
void dfs1(int u){
f[u][0] = 1;
for(P it : G[u]){
int v = it.v;
LL w = it.w;
if(fa[u] == v) continue;
fa[v] = u;
dfs1(v);
W[0] = 1;
for(int i = 1; i <= K; ++i) W[i] = W[i-1] * w % MOD;
for(int j = 0; j <= K; ++j){
for(int k = 0; k <= j; ++k){
add(f[u][j], C[j][k] * f[v][k] % MOD * W[j-k] % MOD);
}
}
}
add(ans, f[u][K]);
}
// 计算g[v][j]
void dfs2(int u){
for(P it : G[u]){
int v = it.v;
LL w = it.w;
if(fa[u] == v) continue;
W[0] = 1;
for(int i = 1; i <= K; ++i) W[i] = W[i-1] * w % MOD;
memset(h, 0, sizeof h);
for(int j = 0; j <= K; ++j){
for(int k = 0; k <= j; ++k){
add(h[j], C[j][k] * f[v][k] % MOD * W[j-k] % MOD);
}
}
memset(t, 0, sizeof t);
for(int j = 0; j <= K; ++j) {
t[j] = g[u][j] + f[u][j] - h[j];
t[j] = (t[j] + MOD) % MOD;
}
for(int j = 0; j <= K; ++j){
for(int k = 0; k <= j; ++k){
add(g[v][j], C[j][k] * W[k] % MOD * t[j-k] % MOD);
}
}
add(ans, g[v][K]);
dfs2(v);
}
}
int main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> K;
int u, v;
LL w;
for(int i = 1; i < n; ++i){
cin >> u >> v >> w;
G[u].push_back((P){v, w});
G[v].push_back((P){u, w});
}
for(int i = 0; i < MAX_K; ++i) C[i][0] = C[i][i] = 1;
for(int i = 2; i < MAX_K; ++i){
for(int j = 1; j < i; ++j){
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
}
}
ans = 0;
dfs1(1);
dfs2(1);
LL inv_ = inv(n);
cout << ans * inv_ % MOD * inv_ % MOD << endl;
return 0;
}