1149D

首先 \(a\) 边可以随便选。 显然，若某条 \(b\) 边的两端位于同一 \(a\) 连通块，一定不会被我们考虑。剩下的 \(b\) 边一定会将两个 \(a\) 连通块相连。 那么此时我们对于 \(b\) 边的约束是，位于一个环上的 \(b\) 边不能同时存在图中，即，我们的路径不能从当前连通块 ......

洛谷传送门 CF 传送门 考虑一条 \(1 \to i\) 的路径是否在最小生成树上。 称边权为 \(a\) 的边为轻边，边权为 \(b\) 的边为重边。 轻边若不成环则一定在最小生成树上，因此先把轻边合并，这样形成了若干连通块。 那么如果两点在一个连通块，它们只能通过轻边互达。 同时，因为是树上路 ......

~~看到 $n\le 70$，想到状压 DP。~~ 首先，显然对于一棵最小生成树，每个轻边连通块内部都是一棵树，轻边连通块缩点后点之间的重边也是一棵树。也就是说，缩点后不存在重边组成的环（包括自环），路径一旦离开了一个轻边连通块就再也不会回来了。 于是先洪水填充求出连通块，设共有 $k$ 个连通块。 ......