\(\mathcal{Description}\)
Link.
在 NOIP 2020 A 的基础上，每条边赋权值 \(a_i\)，随机恰好一条边断掉，第 \(i\) 条段的概率正比于 \(a_i\)。求每个汇集口收集到污水的期望吨数。答案模 \(998244353\)（我谢谢出题人。
\(\mathcal{Solution}\)
方法一 这个题麻烦的地方在于 DAG 上断边，很难将每条断边的贡献一起计算（注意不是“叠加”，仅仅是一下子算出分别断开多条边的贡献之和）。我们得想个办法保持 DAG 的静态结构不变。
考虑若 \(\lang u,v\rang\) 断开，那么到达 \(u\) 的污水量期望 \(x\) 是已知的，且对于除了 \(v\) 之外 \(u\) 的所有后继 \(w\)，流入量都会增加 \(\Delta_1=\frac{x}{d_u(d_u-1)}\)；\(v\) 的流入量会减少 \(\Delta_2=\frac{x}{d_u}\)。当然“所有后继”所含要素过多，我们给它放到 \(u\) 身上，结合 \(\Delta_1,\Delta_2\)，重新描述一下断边的影响：
断掉 \(\lang u,v\rang\)，\(u\) 会获得一条私人流入管道，流入量 \(I_u=\frac{x}{d_u-1}\)；\(v\) 会获得一条私人流出管道，流出量 \(O_v=\frac{x}{d_u(d_u+1)}+\frac{x}{d_u}\)。注意 \(\lang u,v\rang\) 仍然存在且具有正常运输功能。
嗯，DAG 不动了，随便算叭。
方法二 \(\sf OneInDark\) 太厉害辣！
\(f(i,...)\)，表示拓扑序前 \(i\) 个构成的 DAG 中，……
不要被该死的树 DP 限制了，不要一直去想构造子树结构。
两个方法复杂度都是 \(\mathcal O(n+m)\)。
\(\mathcal{Code}\)
方法一。
/*+Rainybunny+*/
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)
inline char fgc() {
static char buf[1 << 17], *p = buf, *q = buf;
return p == q && (q = buf + fread(p = buf, 1, 1 << 17, stdin), p == q)
? EOF : *p++;
}
inline int rint() {
int x = 0, s = fgc();
for (; s < '0' || '9' < s; s = fgc());
for (; '0' <= s && s <= '9'; s = fgc()) x = x * 10 + (s ^ '0');
return x;
}
inline void wint(const int x) {
if (9 < x) wint(x / 10);
putchar(x % 10 ^ '0');
}
const int MAXN = 2e5, MAXM = 5e5, MOD = 998244353;
int n, A, B, m, sum, ecnt, head[MAXN + 5];
int ideg[MAXN + 5], odeg[MAXN + 5], osum[MAXN + 5];
int inv[MAXM + 5], que[MAXN + 5], hd, tl, f[MAXN + 5], g[MAXN + 5];
struct Edge { int to, old, nxt; } graph[MAXM + 5];
inline void link(const int s, const int t, const int o) {
graph[++ecnt] = { t, o, head[s] }, head[s] = ecnt;
}
inline int mul(const int u, const int v) { return 1ll * u * v % MOD; }
inline void subeq(int& u, const int v) { (u -= v) < 0 && (u += MOD); }
inline void addeq(int& u, const int v) { (u += v) >= MOD && (u -= MOD); }
inline int sub(int u, const int v) { return (u -= v) < 0 ? u + MOD : u; }
inline int add(int u, const int v) { return (u += v) < MOD ? u : u - MOD; }
inline int mpow(int u, int v) {
int ret = 1;
for (; v; u = mul(u, u), v >>= 1) ret = mul(ret, v & 1 ? u : 1);
return ret;
}
int main() {
freopen("water.in", "r", stdin);
freopen("water.out", "w", stdout);
n = rint(), A = rint(), B = rint(), m = rint();
rep (i, 1, m) {
int s = rint(), t = rint(), a = rint();
link(s, t, a), ++ideg[t], ++odeg[s], addeq(osum[s], a), addeq(sum, a);
}
inv[1] = 1, sum = mpow(sum, MOD - 2);
rep (i, 2, m) inv[i] = mul(MOD - MOD / i, inv[MOD % i]);
hd = 1;
rep (i, 1, A) que[++tl] = i, f[i] = g[i] = 1;
while (hd <= tl) {
int u = que[hd++], dlt = mul(f[u], mul(inv[odeg[u]],inv[odeg[u] - 1]));
addeq(g[u], mul(mul(osum[u], sum), mul(dlt, odeg[u])));
// extra input [cut(u,?)].
for (int i = head[u], v; i; i = graph[i].nxt) {
if (!--ideg[v = graph[i].to]) que[++tl] = v;
addeq(f[v], mul(f[u], inv[odeg[u]])); // normally flow.
addeq(g[v], mul(g[u], inv[odeg[u]])); // normally flow.
subeq(g[v], mul(mul(graph[i].old, sum), // extra output [cut(u,v)].
add(dlt, mul(f[u], inv[odeg[u]]))));
}
}
rep (i, n - B + 1, n) printf("%d%c", g[i], i < n ? ' ' : '\n');
return 0;
}