[ARC093E]Bichrome Spanning Tree | K-D Space

[EndSaH]

https://endsah.cf/blog/ARC093E-Bichrome-Spanning-Tree/

Description给定一个 $n$ 点 $m$ 边的无向连通图，现需要对每条边染黑或白色。 定义一棵生成树合法，当且仅当其至少有一条黑边和白边。 问有多少种染色方案满足最终图中合法的最小生成树的权值等于 $x$。 $$1 \le n \le 1000, 1 \le m \le 2000, 1 \le x \le 10 ^{12} \\texttt{Bonus:} 1 \le n \le 5