表示以為根的子樹中到所有(子樹中的節(jié)點)的路徑和的次方的和。
可以得到一個動態(tài)轉(zhuǎn)移方程:
考慮二項式展開:

類似的:

所以通過這個性質(zhì)可以得到動態(tài)轉(zhuǎn)移方程:
記表示節(jié)點的父親結(jié)點.表示之間的權(quán)值

得到了從結(jié)點到它的子樹的結(jié)點的路徑次方權(quán)值和之后,我們還需要計算從結(jié)點到它除去它的子樹的結(jié)點也就是它的父親的那邊的那些結(jié)點的路徑次方權(quán)值和。

表示從結(jié)點v到除去結(jié)點的子樹中的結(jié)點(也就是到的父親結(jié)點那個方向的結(jié)點)邊權(quán)的次方的和

記結(jié)點的父親結(jié)點是.

記和之間的邊權(quán)是

所以我們可以得到動態(tài)轉(zhuǎn)移方程.

(備注:關(guān)于這個動態(tài)轉(zhuǎn)移方程的解釋如下)

表示從結(jié)點到父親結(jié)點方向的次方權(quán)值和.

表示從結(jié)點到它的子樹方向結(jié)點的次方權(quán)值和.

現(xiàn)在是的一個孩子結(jié)點.

那么通過我們計算得到的上面式子的就是從結(jié)點出發(fā)到除去為根的子樹的結(jié)點(包括)的所有結(jié)點的次方權(quán)值和.我們現(xiàn)在要算從出發(fā)到除去自己子樹下面的結(jié)點的次方權(quán)值和.再加上到之間的權(quán)值的次方即可

所以最后答案顯然是:

當(dāng)然計算過程中要進(jìn)行取模運(yùn)算，以及最后的要進(jìn)行模逆元的運(yùn)算。

#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;
}