我曾经以为$LCT$已经足够毒瘤，直到我写了树套树。

我曾经又以为树套树已经足够毒瘤，直到我写了这道题。

$hhh$

这道题大概分为三个部分

 

一、首府之间最近点相连

由于$N$不超过$10^5$，且$|X_i|,|Y_i|$均匀随机，我们大可以使用$KD-Tree$，即先以每个州首府坐标建出$KD-Tree$，再枚举每一个点进行在$KD-Tree$中搜索，由于坐标随机，复杂度期望为$O(N\log N)$。

这里有一个性质，那就是一定不存在重边以外的简单环。因为如果存在，那么你一定能找到一个不符合要求的点，所以这样连出来的一定是树或森林。如果有重边，那么很显然若我们要割掉它，必须把两条边全部割掉，即把所有重边变成一条边，这条新的边权值是原来重边的和。并且在后续计算答案时，若两个点所在的州不在同一个连通块上，那么答案为$0$，因为本身就不联通，这个用并查集维护即可。

 

二、预处理最小割树$(Gomory\space Tree)$

最小割树基于一个非常重要的理论:在$n$个点的无向图中，本质不同的割至多有$n-1$个。利用这个性质，我们可以将这个无向图重构成一棵树，每一条树边代表一种割的方案的代价。

具体的方法就是，设一开始所有的点都在同一个点集中，然后随便选一个点数大于$1$的点集$S$，从$S$中任取两点$a,b$，以$a,b$为源汇跑最小割，然后把$S$中和$a$在割集同一侧的点单独拿出来，$S$中剩下的点一定和$b$在割集的同一侧，这样产生了两个$S$的非空子集$S_1,S_2$，并且在重构的树上建立一条$(a,b)$权值为割集大小的树边，然后将$S_1,S_2$递归处理直到$|S|=1$为止，这样，任意两个点最小割就是在重构树上两个点的路径上最小的边权。虽然说这样的复杂度可能达到$O(Dinic\sum n_i^2)$，这道题并没有其他更可行的做法......，不过在我写到这里的时候，隔壁的$julao$  走了过来告诉我这个复杂度是可以用均值不等式来证明在$Dinic$够快的情况下是合法的。

 

三、大小树跑倍增

大树就是每一个首府连成的树，小树就是每个州内部的最小割树，只是用倍增维护一下路径最小值而已，非常简单，没啥可说的。

 

来吧，面对疾风吧。

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define LL long long#define mid ((l+r)>>1)#define INF 1000000000#define N 100200#define HA mainusing namespace std;namespace IO{    const int SS=(1<<20)+5;    char buf[SS],*H,*K;    inline char Get(){        if(H==K) K=(H=buf)+fread(buf,1,SS,stdin);        if(H==K) return -1;return *H++;    }    inline int read(){        int x=0,fg=1;char c=Get();        while(!isdigit(c)&&c!='-') c=Get();        if(c=='-') fg=-1,c=Get();        while(isdigit(c)) x=x*10+c-'0',c=Get();        return x*fg;    }    char obuf[SS],*oS=obuf,*oT=oS+SS-1,c,qu[55];int qr;    inline void flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}    inline void putc(char x){*oS++ =x;if(oS==oT) flush();}    void print(int x){        if(!x) putc('0');        if(x<0) putc('-'),x=-x;        while(x) qu[++qr]=x%10+'0',x/=10;        while(qr) putc(qu[qr--]);        putc('\n');    }}using namespace IO;int sq(int x){return x*x;}int n,m,fs[N],nt[N<<1],to[N<<1],len[N<<1],dt[N],ot[N],vis[N],kd;int u[N<<6],v[N<<6],w[N<<6],V[N][2],E[N][2],tmp,now;int res[N],G[N][18],P[N][18],D[N];struct node{    int id,c[2]; node(){}    node(int _id,int _c0,int _c1){id=_id,c[0]=_c0,c[1]=_c1;}    void gtin(int x){c[0]=read(),c[1]=read(),id=x;}    bool operator <(const node&ot)const{return c[kd]
          
           mx[x][i]) tt+=sq(mx[x][i]-k.c[i]); } return tt; } void update(int x,int from){ if(from==0) return; mx[x][0]=max(mx[x][0],mx[from][0]),mx[x][1]=max(mx[x][1],mx[from][1]); mi[x][0]=min(mi[x][0],mi[from][0]),mi[x][1]=min(mi[x][1],mi[from][1]); } void pushup(int x){gt(x,p[t[x]]),update(x,L[x]),update(x,R[x]);} void build(int &x,int l,int r,int nw){ x=++cnt,L[x]=R[x]=0; m=nw,nth_element(p+l,p+mid,p+r+1);t[x]=mid,gt(x,p[t[x]]); if(l
           
            0) val[ot[i]]+=val[i],val[i]=0; else lk(i,ot[i],val[i]),lk(ot[i],i,val[i]),F[fd(i)]=fd(ot[i]); } for(int i=1;i<=n;i++) if(fd(i)==i) DFS(i,0,0); } int minn(int x,int y){ if(fd(x)!=fd(y)) return 0; if(dep[x]
            
             =0;j--){ if(dep[fa[x][j]]
             
              =0;j--){ if(fa[x][j]==fa[y][j]) continue; now=min(now,min(W[x][j],W[y][j])); x=fa[x][j],y=fa[y][j]; } while(x!=y) now=min(now,min(W[x][0],W[y][0])),x=fa[x][0],y=fa[y][0]; return now; } void RUN(){build(Root,1,n,0);cover();}}Cap;struct Gomory_tree{ int cur[N],S,T,rem[N],q[N],hd,tl,tt[N],pos[N],col[N],tot,sz,nw; void addedge(int x,int y,int rm){ nt[tmp]=fs[x],fs[x]=tmp,to[tmp]=y,rem[tmp++]=rm; nt[tmp]=fs[y],fs[y]=tmp,to[tmp]=x,rem[tmp++]=rm; } void init(int B){ tot=E[B][1]-E[B-1][1],sz=V[B][1]-V[B-1][1]; for(int i=1;i<=sz;i++) fs[i]=-1,pos[i]=i; tmp=0,nw=E[B][0]; for(int i=E[B][0];i<=E[B][1];i++) addedge(u[i],v[i],w[i]); } bool BFS(){ for(int i=1;i<=sz;i++) cur[i]=fs[i],vis[i]=-2; hd=tl=0,vis[S]=1,q[tl++]=S; while(hd
              
               =0) continue; vis[to[i]]=vis[x]+1,q[tl++]=to[i]; } } return vis[T]>0; } int dfs(int x,int mxf){ if(x==T||!mxf) return mxf; int temp=0; for(int &i=cur[x];i!=-1;i=nt[i]){ if(rem[i]==0||vis[to[i]]!=vis[x]+1) continue; int lc=min(mxf-temp,rem[i]); int rc=dfs(to[i],lc); rem[i]-=rc,rem[i^1]+=rc,temp+=rc; if(temp==mxf) break; } if(temp==0) vis[x]=-2; return temp; } int dinic(){int as=0;while(BFS()) as+=dfs(S,INF);return as;} void clr(){ for(int i=0,sum;i
               
                >1); for(int i=1;i<=sz;i++) col[i]=0; } void Paint(int x){ if(col[x]) return; col[x]=1; for(int i=fs[x];i!=-1;i=nt[i]) if(rem[i]) Paint(to[i]); } void solve(int l,int r){ if(l==r) return; clr(); S=pos[l],T=pos[r],w[nw]=dinic(); int t1=l,t2=r; u[nw]=S,v[nw]=T,nw++; Paint(S); for(int i=l;i<=r;i++){ if(col[pos[i]]) tt[t1++]=pos[i]; else tt[t2--]=pos[i]; } for(int i=l;i<=r;i++) pos[i]=tt[i]; solve(l,t2),solve(t1,r); } void check(int x){init(x),solve(1,sz);}}Cut;void getdep(int x,int last,int from){ res[x]=min(res[last],from); P[x][0]=last,G[x][0]=from,D[x]=D[last]+1; for(int j=1;j<18;j++){ P[x][j]=P[P[x][j-1]][j-1]; G[x][j]=min(G[x][j-1],G[P[x][j-1]][j-1]); } for(int i=fs[x];i!=-1;i=nt[i]) if(to[i]!=last) getdep(to[i],x,len[i]);}int getans(int B1,int t1,int B2,int t2){ if(Cap.fd(B1)!=Cap.fd(B2)) return 0; if(B1==B2){ int fin=INF,x=t1+V[B1-1][1],y=t2+V[B1-1][1]; if(D[x]
                
                 =0;j--){ if(D[P[x][j]]
                 
                  =0;j--){ if(P[x][j]==P[y][j]) continue; fin=min(fin,min(G[x][j],G[y][j])); x=P[x][j],y=P[y][j]; } if(x!=y) fin=min(fin,min(G[x][0],G[y][0])); return fin; } int fin=min(res[t1+V[B1-1][1]],res[t2+V[B2-1][1]]); return min(fin,Cap.minn(B1,B2));}int HA(){ n=read(),memset(fs,-1,sizeof(fs)); memset(dt,0x3f,sizeof(dt)),Cap.iit(); for(int i=1;i<=n;i++){ p[i].gtin(i),Cap.val[i]=read(); V[i][0]=V[i][1]=V[i-1][1];E[i][0]=E[i][1]=E[i-1][1]; V[i][0]++,E[i][0]++,V[i][1]+=read(),E[i][1]+=read(),res[V[i][0]]=INF; for(int j=E[i][0];j<=E[i][1];j++) u[j]=read(),v[j]=read(),w[j]=read(); } Cap.RUN(),res[0]=INF; for(int i=1;i<=n;i++) Cut.check(i); memset(fs,-1,sizeof(fs)),tmp=0; for(int i=1;i<=n;i++){ for(int j=E[i][0];j