[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 \times 10 ^5, 1 \le m \le 10 ^6
$$

2019-10-8

Solution

设 $f(lim)$ 表示最终图中合法最小生成树的权值大于等于 $lim$ 的方案。答案可表示为 $f(X) - f(X + 1)$。

现在考虑怎么求出 $f(lim)$。

首先建出最小生成树,若其权值 $sum$ 大于等于 $lim$,则 $2 ^m - 2$ 种染色方案均合法(除了全部同色的情况之外)。

否则,易知最小生成树的边必然全部同色。此时再考虑破圈算法,即枚举一条非树边 $(u, v, w)$,在最小生成树上找到 $u, v$ 路径上的最大边权 $p$,如果 $sum - p + w$ 仍小于 $lim$,则说明这条边也应当与最小生成树上的边同色,否则就可以得到一个合法的权值小于 $lim$ 的生成树。

有一个这样的问题:有没有可能存在两棵权值相同的最小生成树 $A, B$,使得某条非树边在 $A$ 中可以破圈得到小于 $lim$ 的生成树,而在 $B$ 中无法得到?

结合「最小生成树一定是最小瓶颈生成树」的结论可以得到这是不可能的。

假设最终得到有 $cnt$ 条边必须同色,那么最终方案数即 $2 ^{m - cnt + 1} - 2$。

树上路径最大值可以直接倍增求解,时空复杂度 $O(n \log n)$。

Code

gen

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from random import randint
from cyaron import *
import os
cnt = 0
while True :
T = 5
outs = "%d\n" % T
for o in range(T) :
n = 10
m = randint(n, n * (n - 1) // 2)
X = randint(1, 100)
outs += "%d %d %d\n" % (n, m, X)
graph = Graph.UDAG(n, m, self_loop = False, repeated_edges = False, weight_limit = (1, 15))
outs += graph.to_str() + '\n'
print(outs, file = open("zhuzhu.in", "w"))
os.system("./std && ./zhuzhu")
if os.system("diff zhuzhu.out zhuzhu.ans") :
print("WA")
exit()
else :
cnt += 1
if cnt % 100 == 0 :
print("AC %d times!" % cnt)

std

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include <cstdio>
#include <cstring>
#include <iostream>
#include <bitset>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxN = 1e5 + 5;
const int maxM = 2e5 + 5;
const int mod = 1e9 + 7;

int n, m, T, ecnt;
int head[maxN], dep[maxN];
int to[maxM], nxt[maxM], wht[maxM];
int f[20][maxN], MAX[20][maxN];
LL X, mstsum;
bitset<maxM> ismst, vis;

struct Edge
{
int u, v, w;

Edge() { }

Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) { }
} edge[maxM];

bool operator<(const Edge& a, const Edge& b)
{ return a.w < b.w; }

template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

namespace U
{
int fa[maxN], size[maxN];

int Find(int x)
{ return fa[x] == x ? x : fa[x] = Find(fa[x]); }

inline bool Merge(int u, int v)
{
int fu = Find(u), fv = Find(v);
if (fu == fv)
return false;
if (size[fu] > size[fv])
swap(fu, fv);
fa[fu] = fv, size[fv] += size[fu];
return true;
}

void Init()
{
for (int i = 1; i <= n; ++i)
fa[i] = i, size[i] = 1;
}
}

int FPM(int bas, int ind)
{
int res = 1;
while (ind)
{
if (ind & 1)
res = (LL)res * bas % mod;
bas = (LL)bas * bas % mod;
ind >>= 1;
}
return res;
}

void DFS(int u)
{
for (int i = 1; 1 << i <= dep[u]; ++i)
f[i][u] = f[i - 1][f[i - 1][u]],
Chkmax(MAX[i][u] = MAX[i - 1][u], MAX[i - 1][f[i - 1][u]]);
for (int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if (v == f[0][u])
continue;
f[0][v] = u, MAX[0][v] = wht[i];
dep[v] = dep[u] + 1;
DFS(v);
}
}

int Query(int u, int v)
{
int res = 0;
if (dep[u] < dep[v])
swap(u, v);
for (int i = 19; ~i; --i)
if (dep[f[i][u]] >= dep[v])
Chkmax(res, MAX[i][u]), u = f[i][u];
if (u == v)
return res;
for (int i = 19; ~i; --i)
if (f[i][u] != f[i][v])
{
Chkmax(res, MAX[i][u]);
u = f[i][u];
Chkmax(res, MAX[i][v]);
v = f[i][v];
}
return max(res, max(MAX[0][u], MAX[0][v]));
}

inline void Link(int u, int v, int w)
{
++ecnt;
to[ecnt] = v, wht[ecnt] = w, nxt[ecnt] = head[u];
head[u] = ecnt;
++ecnt;
to[ecnt] = u, wht[ecnt] = w, nxt[ecnt] = head[v];
head[v] = ecnt;
}

inline void Init()
{
memset(head + 1, 0, n * sizeof(int));
ecnt = 0, mstsum = 0;
memset(f, 0, sizeof(f));
memset(MAX, 0, sizeof(MAX));
ismst.reset();
}

int Getans(LL lim)
{
if (mstsum >= lim)
return FPM(2, m) - 2;
vis.reset();
for (int i = 1; i <= m; ++i) if (!ismst[i])
{
int u = edge[i].u, v = edge[i].v;
if (mstsum + edge[i].w - Query(u, v) < lim)
vis.set(i);
}
return FPM(2, m - vis.count() - n + 2) - 2;
}

int main()
{
freopen("zhuzhu.in", "r", stdin);
freopen("zhuzhu.out", "w", stdout);
ios::sync_with_stdio(false);
cin >> T;
while (T--)
{
cin >> n >> m >> X;
for (int i = 1; i <= m; ++i)
{
Edge& o = edge[i];
cin >> o.u >> o.v >> o.w;
}
sort(edge + 1, edge + m + 1);
U::Init(), Init();
for (int i = 1; i <= m; ++i)
{
Edge& o = edge[i];
if (U::Merge(o.u, o.v))
{
ismst.set(i);
Link(o.u, o.v, o.w);
mstsum += o.w;
}
}
dep[1] = 1, DFS(1);
cout << ((Getans(X) - Getans(X + 1)) % mod + mod) % mod << endl;
}
return 0;
}