P12041 [USTCPC 2025] 图上交互题 2 / Constructive Minimum Mex Path
显然 \(f(u,v)\) 只有 \(0\) 和 \(1\) 两种取值。
当 \(f(u,v) = 1\) 时，显然有 \(w(u,v) = 0\)，且 \(u \to v\) 的任意路径上，都存在边权为 \(0\) 的边。记删掉所有边权为 \(0\) 的边后新图为 \(G\)，则 \(G(u, v)\) 不连通。
当 \(f(u,v) = 0\) 时， 即 \(u \to v\) 的任意路径上，存在至少一条路径满足不存在边权为 \(0\) 的边，此时 \(G(u, v)\) 连通，另 \(w(u,v) = 1\) 不会使图 \(G\) 的连通性更优。