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;
}