Solution -「多校聯訓」排水系統

\(\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)\)。

  方法一。