[BZOJ 3669][NOI 2014]魔法森林(Link-Cut Tree) - c++编程基础

记得四个月之前的NOI同步赛，我还只会玩脚丫子。。。。

记得我当时看到这个题整个人就吓傻了，完全不知道怎么做，然后NOI同步赛就这样爆零了。。。

如今我学了LCT这个神器，再看这个题，感觉不再那么难了。

其实这个题的标准解法是SPFA，改得完全认不出来的SPFA。

orz太神了，完全没见识过这么神?的SPFA，NOIP 2014考了SPFA，NOI 2014也考了SPFA，原来SPFA也能玩出这么多花样。

我只会用LCT暴力这题，我会暴力我自豪。然后我orz了hzwer的本题lct版本代码和bin神的lct模板，自己yy乱弄了下过了这个题。

下面是我的思路，如有错误请不吝指教。

first of all，我们要构造下这题的LCT，在这题中，图有n个点m条边，于是lct里，下标在[1,n]的结点都是图中的点，下标在(n,m+n]中的结点都是图中的边，只有边对应的结点有权值，这个权值就是对应的边的b值。

然后我们用类似kruscal的方法，将每个边按照关键字a值升序排序，然后搞个并查集，维护图的连通性。

接着，我们像搞最小生成树一样，按a值从小到大不断地加边，维护并查集，加一条边时，要同时在LCT里连接这条边的两个点u和v，具体做法是先连接u和边对应的结点，再把边对应的结点和v相连。

在这个过程中，如果出现遍历到一条边u-v时，u-v本身是联通的，那么我们不加此边，但是要看LCT中u到v路径上的最大权值是不是大于这条边的b值，若是的话，则需要断掉u到v路径上最大权值的那条边的连接，加入这条边。

最后，答案就是min(a+LCT中起点对应结点到终点对应结点路径上的最大权值之和)。

PS：忍不住吐槽下，我第一次WA掉居然是因为splay操作最后忘了上传标记，orzorz。。。。。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define MAXN 150050 #define MAXE 100005 #define INF 0x3f3f3f3f using namespace std; struct edge { int u,v,a,b; }edges[MAXE]; int n,m,nCount=0,ans=INF; int f[MAXN]; int ch[MAXN][2],fa[MAXN]; int val[MAXN],maxv[MAXN]; //该点值的标记、该点对应区间的最大值对应结点的下标 bool rev[MAXN]; //翻转标记 bool isRoot[MAXN]; //根节点标记 int findSet(int x) { if(f[x]==x) return x; return f[x]=findSet(f[x]); } bool operator<(edge a,edge b) { return a.a
       
        val[maxv[r]]) maxv[r]=maxv[lc]; if(val[maxv[rc]]>val[maxv[r]]) maxv[r]=maxv[rc]; } void rotate(int x) //将x旋到上面一层去 { int y=fa[x],kind=ch[y][1]==x; ch[y][kind]=ch[x][!kind]; fa[ch[y][kind]]=y; fa[x]=fa[y]; fa[y]=x; ch[x][!kind]=y; if(isRoot[y]) //y是根节点，则需要更新根节点标记 { isRoot[y]=false; isRoot[x]=true; } else ch[fa[x]][ch[fa[x]][1]==y]=x; pushup(y); } void P(int r) //维护r和它的祖先们 { if(!isRoot[r]) P(fa[r]); pushdown(r); } void splay(int r) //将r旋到根节点上去 { P(r); while(!isRoot[r]) { int f=fa[r],ff=fa[f]; //父结点、祖父结点 if(isRoot[f]) rotate(r); else if((ch[ff][1]==f)==(ch[f][1]==r)) //r、r的父亲、r的祖父三点共线 rotate(f),rotate(r); else rotate(r),rotate(r); } pushup(r); } //End Of Splay //Start Of Link-Cut Tree int access(int x) //打通x到根节点的偏爱路径 { int y=0; do { splay(x); isRoot[ch[x][1]]=true; isRoot[ch[x][1]=y]=false; pushup(x); x=fa[y=x]; }while(x); return y; } void memroot(int r) //使r成为所在树的根 { access(r); splay(r); updateRev(r); } void link(int u,int v) //link操作 { memroot(u); fa[u]=v; } void cut(int u,int v) //cut操作 { memroot(u); access(v); splay(v); fa[ch[v][0]]=fa[v]; fa[v]=0; isRoot[ch[v][0]]=true; ch[v][0]=0; pushup(v); } //End Of Link-Cut Tree int query(int x,int y) //求点x到y之间路径上的最大值 { memroot(x); access(y); splay(y); return maxv[y]; } void solve(int k) //如果边k链接的两边的点u和v本身联通，而且u到v路径上的最大的b值比边k的b值大，则用边k去代替点u到v的路径 { int u=edges[k].u,v=edges[k].v,w=edges[k].b; int t=query(u,v); if(w
        
         ? ??