[Aug4] Blink

tot没清空…


题意

有一棵n个点带边权的树。求随机选k个点环游的花费期望。

思路

首先对于一条边如果被经过一定是被经过两次(来一次回一次)。

所以对每条边进行分析。

一条边被选中的概率是1-全选一边子树的概率-全选另一边子树概率。

然后dfs()一次求所有子树的size,预处理组合数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 100010,MOD = 998244353;
int head[N],next[N << 1],to[N << 1],val[N << 1],tot = 0;
inline void addedge(int u,int v,int w)
{
next[++tot] = head[u];to[tot] = v;val[tot] = w;head[u] = tot;
next[++tot] = head[v];to[tot] = u;val[tot] = w;head[v] = tot;
}
inline int qpow(int a,int b,int p)
{
int r = 1;for(;b;b >>= 1)
{
if(b & 1) r = 1LL * r * a % p;
a = 1LL * a * a % p;
}
return r;
}
int frc[N],inv[N];
inline void init()
{
frc[0] = 1;for(int i = 1;i < N;i++) frc[i] = 1LL * frc[i - 1] * i % MOD;
inv[N - 1] = qpow(frc[N - 1],MOD - 2,MOD);for(int i = N - 1;~i;i--) inv[i - 1] = (1LL * inv[i] * i % MOD);
}
inline int C(int m,int n)
{
if(m > n) return 0;
return 1LL * (1LL * frc[n] * inv[m] % MOD) * inv[n - m] % MOD;
}
int n,k,siz[N],ckn,ans;
inline void U(int &x,int y){if((x += y) >= MOD) x -= MOD;}
inline void D(int &x,int y){if((x -= y) < 0) x += MOD;}
inline void dfs(int u,int fa)
{
siz[u] = 1;
for(int i = head[u],v = to[i];~i;v = to[i = next[i]])
{
if(v == fa) continue;
dfs(v,u);
int ret = ckn;
D(ret,C(k,siz[v]));D(ret,C(k,n - siz[v]));
U(ans,2LL * ret * val[i] % MOD);
siz[u] += siz[v];
}
}
int main()
{
init();
int T = getint();while(T--)
{
memset(head,-1,sizeof(head));
n = getint();k = getint();
for(int i = 1;i < n;i++)
{
int u = getint(),v = getint(),w = getint();
addedge(u,v,w);
}
ckn = C(k,n);
ans = 0;
dfs(1,0);
printf("%d\n",1LL * ans * qpow(ckn,MOD - 2,MOD) % MOD);
}
return 0;
}