银联高校极客挑战赛-复赛-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;
}