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

· · 个人记录

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

求染色方案数，答案对 10^9+7 取模。

------------ - 考虑给出一张黑白图如何求出同时包含有黑边和白边的最小生成树。 先求一棵最小生成树，若全白或全黑，则枚举一条异色的非树边尝试加入即可。 先求出原图的任意一棵最小生成树，记其边权和为 $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]

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

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

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

对于那些 T_i>X 的 c_2 条边，无限制。

故方案数为 2(2^{c_0}-1)2^{c_2}

若最小生成树不纯色，则必然合法。这部分方案数是 (2^{n-1}-2)2^{m-n+1}

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

复杂度 O(n\log n)。（这个数据范围怎么回事啊）

#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;
}