[??记录]AT3980 [ARC093C] Bichrome Spanning Tree

**题意** ： 在一张无向图上给边黑白染色，使得同时包含有黑边和白边的最小生成树权值恰好为 $X$。 求染色方案数，答案对 $10^9+7$ 取模。 $n\leq 1000,m\leq 2000$ ，时限$\texttt{2s}$. ------------ - 考虑给出一张黑白图如何求出同时包含有黑边和白边的最小生成树。 先求一棵最小生成树，若全白或全黑，则枚举一条异色的非树边尝试加入即可。 先求出原图的任意一棵最小生成树，记其边权和为 $S$。 记下 ${\rm pathmx}(u,v)$ 表示生成树 $u,v$ 路径之间的边权最大值。 上对于非树边 $l_i=(u\leftrightarrow v):w$ , 若将其加入生成树，则生成树边权和变为 $T_i=S-{\rm pathmx}(u,v)+w$。 计算各个 $T_i$ ，记 $c_0=\sum[T_i=X],\ c_1\sum[T_i<X],\ c_2\sum[T_i>X]$ - $S>X$ : 方案数为 $0$。 - $S<X$ 此时必然要拆掉原来的最小生成树，则最小生成树必为纯色。 对于那些 $T_i=X$ 的 $c_0$ 条边，要选某一条加入生成树，不能都为相同的纯色。 对于那些 $T_i<X$ 的 $c_1$ 条边，不能让他们加入生成树，故都为相同的纯色。 对于那些 $T_i>X$ 的 $c_2$ 条边，无限制。 故方案数为 $2(2^{c_0}-1)2^{c_2}$ - $S=X$ 若最小生成树不纯色，则必然合法。这部分方案数是 $(2^{n-1}-2)2^{m-n+1}$ 若最小生成树纯色，计算方法和上一种情况类似。 复杂度 $O(n\log n)$。（~~这个数据范围怎么回事啊~~） ```cpp #include<algorithm> #include<cstdio> #include<vector> #define pb push_back #define ll long long #define MaxN 100500 #define MaxM 200500 using namespace std; const int mod=1000000007; vector<int> g[MaxN],l[MaxN]; void adl(int u,int v,int w) {g[u].pb(v);l[u].pb(w); g[v].pb(u);l[v].pb(w);} int dep[MaxN],f[18][MaxN],c[18][MaxN]; void dfs(int u) { for (int i=0,v;i<g[u].size();i++) if (!dep[v=g[u][i]]){ f[0][v]=u;c[0][v]=l[u][i]; dep[v]=dep[u]+1;dfs(v); } } int lca(int u,int v) { if (dep[u]<dep[v])swap(u,v); for (int k=16;k--;) while(dep[f[k][u]]>=dep[v]) u=f[k][u]; if (u==v)return u; for (int k=16;k--;) while(f[k][u]!=f[k][v]) {u=f[k][u];v=f[k][v];} return f[0][u]; } int _pmx(int u,int lim) { int ret=0; for (int k=16;k--;) while(dep[f[k][u]]>=lim){ ret=max(ret,c[k][u]); u=f[k][u]; } return ret; } int pmx(int u,int v) { int sav=dep[lca(u,v)]; return max(_pmx(u,sav),_pmx(v,sav)); } struct UFS{ int f[MaxN]; void Init(int n) {for (int i=1;i<=n;i++)f[i]=i;} int find(int u) {return f[u]==u ? u : f[u]=find(f[u]);} bool merge(int u,int v){ u=find(u);v=find(v); if (u==v)return 0; f[u]=v;return 1; } }F; struct Line{int u,v,w;bool vis;}b[MaxM]; bool cmp(const Line &A,const Line &B) {return A.w<B.w;} int n,m,pw2[MaxM],c0,c2; ll X,S; int main() { scanf("%d%d%lld",&n,&m,&X); F.Init(n);pw2[0]=1; for (int i=1;i<=m;i++)pw2[i]=(pw2[i-1]<<1)%mod; for (int i=1;i<=m;i++) scanf("%d%d%d",&b[i].u,&b[i].v,&b[i].w); sort(b+1,b+m+1,cmp); for (int i=1;i<=m;i++) if (F.merge(b[i].u,b[i].v)){ adl(b[i].u,b[i].v,b[i].w); b[i].vis=1;S+=b[i].w; } if (S>X){puts("0");return 0;} dep[1]=1;dfs(1); for (int j=1;j<16;j++) for (int i=1;i<=n;i++){ f[j][i]=f[j-1][f[j-1][i]]; c[j][i]=max(c[j-1][i],c[j-1][f[j-1][i]]); } for (int i=1;i<=m;i++) if (!b[i].vis){ ll T=S-pmx(b[i].u,b[i].v)+b[i].w; if (T==X)c0++; if (T>X)c2++; } int ans=2ll*(pw2[c0]-1)*pw2[c2]%mod; if (S==X)ans=(ans+1ll*(pw2[n-1]-2)*pw2[m-n+1])%mod; printf("%d",ans); return 0; } ```