[bzoj2238]Mst

生成树 最小生成树 图论 树链剖分 线段树

题面

给出一个$n$个点$m$条边的无向带权图，以及$q$个询问，每次询问在图中删掉一条边后图的最小生成树。(各询问间独立，每次询问不对之后的询问产生影响，即被删掉的边在下一条询问中依然存在)

• $n\leq5*10^4,m\leq10^5$

解析

很显然题目是问我们一条边被删掉后，能替代它的边的最小长度是多少。

首先构出一棵最小生成树，
如果边不在树内，直接输出最小生成树边权和就可以了。
然后考虑边在树内应该怎么处理。

有一个比较容易想到的结论：一条非树边，肯定能够完全替代，该边两端点在树上的路径中包含的所有边。
于是把边权化为更深结点的点权，然后树链剖分+线段树，用所有非树边对树边覆盖取$min$即可。

$bug$

• 树链剖分lca那个部分打错了。。。
• 如果图一开始就不联通，要一直$Not\ connected$。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define ls x<<1
#define rs x<<1|1
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
int n,m,q,h[N],cnt,f[N],tot,F[N],d[N],top[N],L[N],R[N],sz[N],tim,id[N],t[N<<2],w[N],tag[N<<2],son[N];
ll s,gu;
struct Edge{int to,nxt,w;}e[N<<1];
struct dat{int u,v,w,bei,id;il bool operator < (const dat &o) const {return w<o.w;}}a[N<<1];
il void add(re int u,re int v,re int w)
{
  e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;
  e[++cnt]=(Edge){u,h[v],w};h[v]=cnt;
}
il void dfs1(re int u,re int fa)
{
  f[u]=fa;d[u]=d[fa]+1;sz[u]=1;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs1(v,u);
      sz[u]+=sz[v];
      if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
il void dfs2(re int u,re int up)
{
  top[u]=up;L[u]=++tim;id[tim]=u;
  if(son[u]) dfs2(son[u],up);
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==f[u]||v==son[u]) continue;
      dfs2(v,v);
    }
  R[u]=tim;
}
il void Modify(re int x,re int l,re int r,re int ql,re int qr,re int w)
{
  if(ql<=l&&r<=qr) {t[x]=min(t[x],w);tag[x]=min(tag[x],w);return;}
  re int mid=l+r>>1;
  if(ql<=mid) Modify(ls,l,mid,ql,qr,w);
  if(qr>mid) Modify(rs,mid+1,r,ql,qr,w);
  t[x]=min(tag[x],min(t[ls],t[rs]));
}
il int Query(re int x,re int l,re int r,re int pos)
{
  if(l==r) return t[x];
  re int mid=l+r>>1;
  if(pos<=mid) return min(tag[x],Query(ls,l,mid,pos));
  return min(tag[x],Query(rs,mid+1,r,pos));
}
il int find(re int x){return x==F[x]?x:F[x]=find(F[x]);}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il bool cmp(re dat x,re dat y){return x.id<y.id;}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();m=gi();
  fp(i,1,n) F[i]=i;
  fp(i,1,m) a[i].u=gi(),a[i].v=gi(),a[i].w=gi(),a[i].id=i;
  q=gi();
  sort(a+1,a+1+m);
  fp(i,1,m)
    {
      re int u=a[i].u,fu=find(u),v=a[i].v,fv=find(v),w=a[i].w;
      if(fu^fv) F[fv]=fu,add(u,v,w),s+=w,++gu;
      else a[i].bei=1;
    }
  if(gu<n-1) {while(q--) puts("Not connected");return 0;}
  dfs1(1,0);dfs2(1,1);
    sort(a+1,a+1+m,cmp);
  memset(t,127,sizeof(t));memset(tag,127,sizeof(tag));
  fp(i,1,m)
    if(a[i].bei)
    {
      re int u=a[i].u,v=a[i].v,w=a[i].w;
      while(top[u]^top[v])
      {
        if(d[top[u]]<d[top[v]]) swap(u,v);
        Modify(1,1,n,L[top[u]],L[u],w);
        u=f[top[u]];
      }
      if(d[u]>d[v]) swap(u,v);
      if(u^v) Modify(1,1,n,L[u]+1,L[v],w); 
    }
  while(q--)
    {
      re int x=gi();
      if(a[x].bei) {printf("%lld\n",s);continue;}
      re int ans=Query(1,1,n,L[(d[a[x].u]>d[a[x].v]?a[x].u:a[x].v)]);
      if(ans==t[0]) {puts("Not connected");continue;}
      printf("%lld\n",s-a[x].w+ans);
    }
  return 0;
}