ARC093C Bichrome Spanning Tree

发表于 更新于 分类于 ， ， 阅读次数：

题意：在一张无向图上给边黑白染色，使得同时包含有黑边和白边的最小生成树权值恰好为 。

求染色方案数，答案对 取模。

，，时限 。

  • 考虑给出一张黑白图如何求出同时包含有黑边和白边的最小生成树。

    先求一棵最小生成树，若全白或全黑，则枚举一条异色的非树边尝试加入即可。

先求出原图的任意一棵最小生成树，记其边权和为 。

记下 表示生成树 路径之间的边权最大值。

上对于非树边 , 若将其加入生成树，则生成树边权和变为 。

计算各个 ，记

  • : 方案数为 。

此时必然要拆掉原来的最小生成树，则最小生成树必为纯色。

对于那些 的 条边，要选某一条加入生成树，不能都为相同的纯色。

对于那些 的 条边，不能让他们加入生成树，故都为相同的纯色。

对于那些 的 条边，无限制。

故方案数为 。

若最小生成树不纯色，则必然合法。这部分方案数是

若最小生成树纯色，计算方法和上一种情况类似。

复杂度 。

（这个数据范围怎么回事啊）