银联高校极客挑战赛 复赛 D.多项式

表示以为根的子树中到所有(子树中的节点)的路径和的次方的和。
可以得到一个动态转移方程:
考虑二项式展开:

类似的:

所以通过这个性质可以得到动态转移方程:
记表示节点的父亲结点.表示之间的权值

得到了从结点到它的子树的结点的路径次方权值和之后,我们还需要计算从结点到它除去它的子树的结点也就是它的父亲的那边的那些结点的路径次方权值和。

表示从结点v到除去结点的子树中的结点(也就是到的父亲结点那个方向的结点)边权的次方的和

记结点的父亲结点是.

记和之间的边权是

所以我们可以得到动态转移方程.

(备注:关于这个动态转移方程的解释如下)

表示从结点到父亲结点方向的次方权值和.

表示从结点到它的子树方向结点的次方权值和.

现在是的一个孩子结点.

那么通过我们计算得到的上面式子的就是从结点出发到除去为根的子树的结点(包括)的所有结点的次方权值和.我们现在要算从出发到除去自己子树下面的结点的次方权值和.再加上到之间的权值的次方即可

所以最后答案显然是:

当然计算过程中要进行取模运算，以及最后的要进行模逆元的运算。

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