最小割树的定义： 定义一棵树T为最小割树，如果对于树上的所有边(s,t)，树上去掉(s,t)后产生的两个集合恰好是原图上(s,t)的最小割把原图分成的两个集合，且边(u,v)的权值等于原图上(u,v)的最小割。

最小割树的性质：原图上u,v两点最小割就是最小割树上u到v的路径上权值最小的边。

我们要知道，最小割树是对于无向图来说的，有向图不存在此树及性质。

我们可以利用 分治的思想去构造最小割树 ，每次随机选两个点，对此两点跑最小割，之后在最小割树上连边。
然后对于跑完之后的残量网络，上面的点集分成了两个集合，然后分别分治下去即可。（最后一次bfs，达不到终点，即增广数组有些点的值为0）

总复杂度为跑n次最小割，复杂度为 n^3 * m 但是我们要知道，最小割的复杂度远远达不到上限。

之后，剪完最小割树之后，求最小边就可以直接树上倍增，或者树剖了。

例题：最小割树例题

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=510,M=1e4+10;
int n,m,q;
struct maxflow{
    int head[N],nex[M],to[M],w[M],h[N],tot=1,s,t;   queue<int> q;  
    inline void ade(int a,int b,int c){
        to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
    }
    inline void add(int a,int b,int c){ade(a,b,c);  ade(b,a,0);}
    inline int bfs(){
        q.push(s);  memset(h,0,sizeof h);   h[s]=1;
        while(q.size()){
            int u=q.front();    q.pop();
            for(int i=head[u];i;i=nex[i]){
                if(w[i]&&!h[to[i]]){
                    h[to[i]]=h[u]+1;    q.push(to[i]);
                }
            }
        }
        return h[t];
    }
    int dfs(int x,int f){
        if(x==t)    return f;   int fl=0;
        for(int i=head[x];i&&f;i=nex[i]){
            if(w[i]&&h[to[i]]==h[x]+1){
                int mi=dfs(to[i],min(w[i],f));
                w[i]-=mi,w[i^1]+=mi,fl+=mi,f-=mi;
            }
        }
        if(!fl) h[x]=-1;
        return fl;
    }
    inline void init(){
    	for(int i=2;i<=tot;i+=2)	w[i]+=w[i^1],w[i^1]=0;
	}
    inline int dinic(){
        int res=0;  init();
        while(bfs())    res+=dfs(s,inf);
        return res;
    }
}d;
struct min_cut_tree{
    int head[N],nex[M],to[M],w[M],tot=0;
    inline void ade(int a,int b,int c){
        to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
    }
    inline void add(int a,int b,int c){ade(a,b,c);  ade(b,a,0);}
    int a[N],b[N],c[N];
    void build(int l,int r){
        if(l==r)    return ;
        d.s=a[l],d.t=a[l+1];    int flow=d.dinic();
        add(a[l],a[l+1],flow);
        int cnt1=0,cnt2=0;
        for(int i=l;i<=r;i++){
            if(d.h[a[i]])   b[++cnt1]=a[i];
            else    c[++cnt2]=a[i];
        }
        for(int i=l;i<=l+cnt1-1;i++)    a[i]=b[i-l+1];
        for(int i=l+cnt1;i<=r;i++)  a[i]=c[i-cnt1-l+1];
        build(l,l+cnt1-1);  build(l+cnt1,r);
    }
    int h[N],f[N][10],mi[N][10],lg[N];
    void dfs(int x,int fa){
        h[x]=h[fa]+1;
        for(int i=1;(1<<i)<=h[x];i++){
            f[x][i]=f[f[x][i-1]][i-1];
            mi[x][i]=min(mi[x][i-1],mi[f[x][i-1]][i-1]);
        }
        for(int i=head[x];i;i=nex[i]){
            if(to[i]==fa)   continue;
            f[to[i]][0]=x; mi[to[i]][0]=w[i];
            dfs(to[i],x);
        }
    }
    void solve(){
        for(int i=1;i<=n;i++)   lg[i]=lg[i-1]+(1<<lg[i-1]==i);
        for(int i=1;i<=n;i++)   a[i]=i;
        build(1,n); dfs(1,0);
    }
    inline int ask(int x,int y){
        int res=inf;
        if(h[x]<h[y])   swap(x,y);
        while(h[x]>h[y]){
            res=min(res,mi[x][lg[h[x]-h[y]]-1]);
            x=f[x][lg[h[x]-h[y]]-1];
        }
        if(x==y)    return res;
        for(int i=lg[h[x]]-1;i>=0;i--){
            if(f[x][i]!=f[y][i]){
                res=min(res,mi[x][i]); res=min(res,mi[y][i]);
                x=f[x][i],y=f[y][i];
            }
        }
        res=min(res,mi[x][0]); res=min(res,mi[y][0]);
        return res;
    }
}mct;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1,a,b,c;i<=m;i++) cin>>a>>b>>c,d.add(a,b,c),d.add(b,a,c);
    mct.solve();
    cin>>q;
    while(q--){
        int a,b;    cin>>a>>b;
        cout<<mct.ask(a,b)<<'\n';
    }
    return 0;
}