bzoj 2238 Mst —— 树剖+mn标记永久化

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2238

看了半天...

首先，想要知道每条边删除之后的替代中最小的那个；

反过来看，每条不在 MST 上的边如果加入，会对一条路径产成影响，具体来说，就是这条路径上的所有边在被删除后，可以考虑用这条非 MST 边替代；

于是就可以用树剖，对每条非 MST 边，维护一下路径上的最小值；

于是写了一下，但WA了，仔细看看，mn 和 lzy 更新的地方似乎有点不太对，比如没有更新 mn 也可以更新 lzy 什么的...(因为 mn 还被左右儿子更新，所以可能比 lzy 更小...)

反正是取min，标记永久化很方便呢(干脆没有 lzy )，于是又跟 Narh 学了一下 mn 标记永久化的写法。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define mid ((l+r)>>1)

#define ls (x<<1)

#define rs (x<<1|1)

using namespace std;

int const xn=,xm=1e5+,inf=0x3f3f3f3f;

int n,m,hd[xn],ct,nxt[xn<<],to[xn<<],dep[xn],siz[xn],son[xn],dfn[xn],top[xn],fa[xn],tim;

int mn[xn<<],lzy[xn<<],ans;

bool use[xm],fl;

struct N{int u,v,w,id;}e[xm];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return f?ret:-ret;

}

void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}

bool cmp(N x,N y){return x.w<y.w;}

bool cmp2(N x,N y){return x.id<y.id;}

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

void dfs(int x)

{

  dep[x]=dep[fa[x]]+; siz[x]=;

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if((u=to[i])==fa[x])continue;

      fa[u]=x; dfs(u); siz[x]+=siz[u];

      if(siz[u]>siz[son[x]])son[x]=u;

    }

}

void dfs2(int x)

{

  dfn[x]=++tim;

  if(son[x])top[son[x]]=top[x],dfs2(son[x]);

  for(int i=hd[x],u;i;i=nxt[i])

    {

      if((u=to[i])==fa[x]||u==son[x])continue;

      top[u]=u; dfs2(u);

    }

}

void pushdown(int x)

{

  if(lzy[x]==-)return;

  if(lzy[x]<mn[ls])mn[ls]=lzy[x],lzy[ls]=lzy[x];

  if(lzy[x]<mn[rs])mn[rs]=lzy[x],lzy[rs]=lzy[x];

  lzy[x]=-;

}

void update(int x,int l,int r,int L,int R,int d)

{

  //  if(l>=L&&r<=R){if(d<mn[x])mn[x]=d,lzy[x]=d; return;}

  //  pushdown(x);

  if(l>=L&&r<=R){mn[x]=min(mn[x],d); return;}

  //  mn[x]=min(mn[x],d);

  if(mid>=L)update(ls,l,mid,L,R,d);

  if(mid<R)update(rs,mid+,r,L,R,d);

  //  mn[x]=min(mn[ls],mn[rs]);

}

void change(int x,int y,int d)

{

  while(top[x]!=top[y])

    {

      if(dep[top[x]]<dep[top[y]])swap(x,y);

      update(,,n,dfn[top[x]],dfn[x],d);

      x=fa[top[x]];

    }

  if(x==y)return;

  if(dep[x]<dep[y])swap(x,y);

  update(,,n,dfn[y]+,dfn[x],d);

}

int query(int x,int l,int r,int pos)

{

  if(l==r)return mn[x];

  //  pushdown(x);

  //  if(pos<=mid)return query(ls,l,mid,pos);

  //  else return query(rs,mid+1,r,pos);

  if(pos<=mid)return min(mn[x],query(ls,l,mid,pos));

  else return min(mn[x],query(rs,mid+,r,pos));

}

int main()

{

  n=rd(); m=rd();

  for(int i=,x,y,z;i<=m;i++)e[i].u=rd(),e[i].v=rd(),e[i].w=rd(),e[i].id=i;

  sort(e+,e+m+,cmp);

  for(int i=;i<=n;i++)fa[i]=i; int cnt=;

  for(int i=;i<=m;i++)

    {

      int x=find(e[i].u),y=find(e[i].v);

      if(x==y)continue;

      add(e[i].u,e[i].v); add(e[i].v,e[i].u); ans+=e[i].w;

      fa[x]=y; cnt++; use[e[i].id]=;//id

      if(cnt==n-)break;

    }

  if(cnt<n-)fl=;

  if(!fl)//省时

    {

      fa[]=; dfs(); top[]=; dfs2();

      memset(mn,0x3f,sizeof mn); memset(lzy,-,sizeof lzy);

      sort(e+,e+m+,cmp2);

      for(int i=;i<=m;i++)

    {

      if(use[i])continue;

      change(e[i].u,e[i].v,e[i].w);

    }

    }

  int q=rd();

  for(int i=,x;i<=q;i++)

    {

      x=rd();

      if(fl){puts("Not connected"); continue;}

      if(!use[x]){printf("%d\n",ans); continue;}

      int k=query(,,n,max(dfn[e[x].u],dfn[e[x].v]));

      if(k==inf)puts("Not connected");

      else printf("%d\n",ans-e[x].w+k);

    }

  return ;

}