CWOI S C0279 C 願

題意

使用 openssl enc -aes256 -pbkdf2 -a 加密。

U2FsdGVkX1+7dJtvmc4+/JZ3n2QkKko46eIHrtdAKya/OZJ1iFWXJDMLEMbOJnnK
IsW5CIWDg7XwnoJ/Bpzv1UXefoDHmpQxlujGmk4qHtpsfRkPpbkN4Jl5vz9IXBBE
nUZFQG4aH427gyk+3FZeQuSnux0Tk33fXnZjm3Vk94DqjGkm7PbHDzZU4l4s57UM
klTF9dW6qxrZGGGzK+vov3pSYYIkmK9d+TgZ4r45r/jgHuGpzzWcik4985vhadpY
p3ycJQNFnDY8a+QV0JUHwPpKrHNshQwfxgxx/xDEW5ylAsVIpWPlFsydRaTy+s2a
RM1toKRj8kg8PD/ZShMm+O52SzIEv649f0qIYeE/geJrZ9c87lomBGKw8Bz5swJ3
S2mfm+eUQvMEZ4FW6ICEUzfvbfA55vGfvdby16OdGIP7F/I/DYNxiEBb6Hir9BIZ
T+hN525CY+EcBT23MDwU9r4+3++Z+igKqbNqqWyhV4SIkAf5X7uF4YRS634kE27v
k30o7q0Kja8tFwmLCPOf6p3kNATrwqG66DKEhE1pFwZeJAlk1tblGD0Z3CPJY2/L
LH30tpu6sshZWXdXbRseINkqd4DlhjkXm2EvxNSNMcedf8tJjVx7TPCcG5S4lbVR
0RmsZX+7uZqrVsaxUHzt4g==

generator

僅作示意

import random
import sys

MAXN = 10**9

if len(sys.argv) != 4:
    print(f"Usage: {sys.argv[0]} n m seed")
    sys.exit(-1)

n = int(sys.argv[1])
m = int(sys.argv[2])
random.seed(sys.argv[3])

print(n, m, MAXN)
for i in range(m):
    print(*random.sample(range(1, n + 1), 2), random.randint(1, MAXN))

解析

可以發現，如果只有這個圖的各個連通塊的瓶頸生成樹上的邊是有用的。我們根據 kruskal 演算法的過程，定義 $f(i, J)$ 表示這個已經加了 $i$ 條邊，$J$ 連通塊（可以當成一個集合，當然實現時可以取並查集中代表元素），所有連通塊中 $h$ 都小於該連通塊最大邊邊權的方案數。令 $g(i, J)$ 表示當前第 $i$ 條邊時 $J$ 連通塊的最大邊， $R$ 表示新增 $u_i - v_i$ 這條邊後的大連通塊，$U$ 表示 $u_i$ 所在連通塊，$V$ 表示 $v_i$ 所在連通塊。轉移方程：

$$f(i, J) = \begin{cases} f(i - 1, J) & J \neq R \\ [f(i - 1, U) + w_i - g(i - 1, U)] \times [f(i - 1, V) + w_i - g(i - 1, V)] \end{cases}$$

實現時可以將這個 dp 的第一維壓掉。

然後考慮統計答案，dp 時，如果 $R$ 中包含 1，那麼就統計上，最後記得把所有不包含 1 的連通塊也統計上。

實現

using mint = static_modint<998'244'353>;
const mint INV2{499'122'177};

struct edge_t
{
	int u, v;
	int w;
};

int main()
{
	int n, m, md;
	std::cin >> n >> m >> md;

	std::vector<edge_t> edges(m);
	for (auto &[u, v, w] : edges) {
		std::cin >> u >> v >> w;
		u--;
		v--;
		w--;
	}

	std::sort(edges.begin(), edges.end(), [](const edge_t &a, const edge_t &b)
		  {
			  return a.w < b.w;
		  });

	std::vector<mint> f(n);
	std::vector<int> g(n);
	dsu d(n);
	mint ans = 0;

	for (auto [u, v, h] : edges) {
		if (d.same(u, v)) continue;
		if (d.same(0, v)) std::swap(u, v);
		int fu = d.find(u);
		int fv = d.find(v);
		if (d.same(0, u)) {
			ans = (ans + mint{g[fu] + h + 1} * mint{h - g[fu]} * INV2) * mint{f[fv] + h - g[fv]};
		}
		int r = d.merge(u, v);
		f[r] = (f[fu] + h - g[fu]) * (f[fv] + h - g[fv]);
		g[r] = h;
	}

	int f0 = d.find(0);
	f[f0] += (md - g[f0]);
	ans += mint{g[f0] + md + 1} * mint{md - g[f0]} * INV2;
	for (int i = 0; i < n; i++) {
		if (!d.is_root(i) || d.same(0, i)) continue;
		f[i] += (md - g[i]);
		ans *= f[i];
		g[i] = md;
	}

	std::cout << ans.val() << std::endl;
}