题目：

看了半天...

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

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

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

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

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

代码如下：

#include
     
      #include
      
       #include
       
        #include
        
         #define mid ((l+r)>>1)#define ls (x<<1)#define rs (x<<1|1)using namespace std;int const xn=50005,xm=1e5+5,inf=0x3f3f3f3f;int n,m,hd[xn],ct,nxt[xn<<1],to[xn<<1],dep[xn],siz[xn],son[xn],dfn[xn],top[xn],fa[xn],tim;int mn[xn<<2],lzy[xn<<2],ans;bool use[xm],fl;struct N{
   int u,v,w,id;}e[xm];int rd(){  int ret=0,f=1; char ch=getchar();  while(ch<'0'||ch>'9'){
   if(ch=='-')f=0; ch=getchar();}  while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',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
         
          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]==-1)return;  if(lzy[x]
          
           =L&&r<=R){if(d
           
            =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