1857g

题目链接 考虑每条非树边的取值，显然不能小于等于该边与树边形成的环中的最大值（当然这条非树边也可以不存在），所以每条非树边的取值范围就是 \(S - max(w) + 1\) （\(+1\)的原因是该边可能不存在）。 暴力枚举肯定会超时，考虑优化。 发现 \(kruskal\) 算法获得最小生成树的 ......

`2023-08-08 23:00:07 solution` ## 题意： 求有多少个有 $n$ 个节点的无向图，使其满足以下条件： - 无重边自环。 - 有且只有一个最小生成树，且为给定树。 - 最大边权不大于 $S$。 对 $998244353$ 取模。 ## 思路： 其实就是让我们在给定的树加 ......

一个非常显然的事情是：总方案数即为每条边方案数之积。 树边已经确定，考察每条非树边 $(u,v)$ 可以怎么取。给定的树 $T$ 是唯一最小生成树，这意味着非树边 $(u,v)$ 要么不存在，要么权值大于 $T$ 上 $(u,v)$ 之间任意一条边的权值。设 $T$ 上 $(u,v)$ 间的最大边权 ......