Solution
发现我们并不关下每一组人到底是哪些人。
不妨从 dp 的角度去考虑这个问题。
设 \(p = 2 / (n \times (n - 1))\)，\(dp_i\) 为选了 \(i\) 组人后期望得到的友谊值。
第 \(i\) 次选人，有 \(1 - p \times m\) 的概率选中不是朋友的一组人。
设 \(x_j\) 为此时第 \(j\) 组的期望友谊值。
可以得到方程：
\[dp_i = dp_{i - 1} + (1 - p \times m) \times 0 + \sum_{j = 1}^{m} p \times x_j \]现在考虑怎么求出 \(x_j\)。
假设一组初始友谊值为 \(t\), \(f_i\) 表示经过 \(i\) 次之后友谊值的期望。
对于一组好朋友，每次有 \(p\) 的概率被选中，友谊值增加 1，有 \(1 - p\) 的概率不被选中，友谊值不变，于是得到：
\[f_i = f_{i - 1} + p \times 1 + (1 - p) \times 0 \]不难发现 \(f_i = t + i \times p\)。
即 \(x_j = f_j + (i - 1) \times p\)。此时 \(f_j\) 的含义为题目所给。
得到：
\[dp_i = dp_{i - 1} + p \times \sum_{j = 1}^{m} (f_j + (i - 1) \times p) \]\[dp_i = dp_{i - 1} + p \times (\sum_{j = 1}^{m} f_j + m \times (i - 1) \times p) \]令 $s = \sum_{i = 1}^{m} f_i $。
\[dp_i = dp_{i - 1} + p \times (s + m \times (i - 1) \times p) \]直接做即可，时间复杂度 \(O(n)\)。
void solve() {
LL n, m, k;
cin >> n >> m >> k;
Z s = 0, p = (Z)2 / (n * (n - 1));
for(int i = 0; i < m; i ++) {
int a, b;
Z c;
cin >> a >> b >> c;
s += c;
}
Z f = 0, g = 0;
for(int i = 0; i < k; i ++) {
f = g + p * (s + m * (Z)i * p);
g = f;
}
cout << f << '\n';
}