在我被这题折磨的时候，我向我的同学求助，他给我发来了代码，让我自行理解。但是，我发现了他只建了一次树，而图不一定联通，这是很明显的错误，但是，他的代码居然过了！

所以请求加强数据

下方是他的代码 @zzl_05

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#define ll long long
#define ri int

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
    ri v = getchar();T f = 1;t = 0;
    while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
    while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
    t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
    read(t);read(args...);
}

template <typename T> inline T min(T x,T y) {return x<y?x:y;}
template <typename T> inline T max(T x,T y) {return x>y?x:y;}
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
const int N = 10010;
const int M = 50010;

int n,m,a[N],s;

int hd[N],nxt[M],edg[M],to[M],tot;
inline void add(int u,int v,int w) {to[++tot] = v;nxt[tot] = hd[u];hd[u] = tot;edg[tot] = w;}
inline void addedge(int u,int v,int w) {add(u,v,w),add(v,u,w);}

struct edge {
    int u,v,w;
    friend inline bool operator < (const edge& a,const edge& b) {
        return a.w > b.w;
    }
}kruskal[M<<1];

int f[N],deg[N];

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

void Kruskal() {
    read(n,m);
    for (int i = 1;i <= m;++i) read(kruskal[i].u,kruskal[i].v,kruskal[i].w);
    for (int i = 1;i <= n;++i) f[i] = i;
    std::sort(kruskal+1,kruskal+1+m);
    for (int i = 1;i <= m;++i) {
        int x = kruskal[i].u,y = kruskal[i].v,z = kruskal[i].w;
        if (find(x) != find(y)) {
            //printf("%d %d\n", x,y);
            f[find(x)] = y;
            addedge(x,y,z);
            ++deg[x],++deg[y];
        }
    }  
    for (int i = 1;i <= n;++i) {if (deg[i] == 1) {s = i;break;}}
    //printf("%d\n", s);
}

int top[N],fa[N],dep[N],siz[N],son[N],dfn[N],rk[N],cnt;

void dfs1(int u,int f) { 
    fa[u] = f;
    dep[u] = dep[f] + 1;
    son[u] = 0;
    siz[u] = 1;
    for (int i = hd[u];i;i = nxt[i]) {
        int v = to[i];
        if (v != f) {
            a[v] = edg[i];
            dfs1(v,u);
            siz[u] += siz[v];
            if (siz[v] > siz[son[u]]) {
                son[u] = v;
            }
        }
    }
}

void dfs2(int u,int f) {
    dfn[u] = ++cnt;rk[cnt] = u;
    if (son[f] == u) top[u] = top[f];
    else top[u] = u;
    if (son[u]) dfs2(son[u],u);
    for (int i = hd[u];i;i = nxt[i]) {
        int v = to[i];
        if (v != f && v != son[u]) {
            dfs2(v,u);
        }
     }
}

struct node {
    int l,r;
    int minn;
}tree[N<<2];

void build(int p,int l,int r) {
    tree[p].l = l,tree[p].r = r;
    if (l == r) {
        tree[p].minn = a[rk[l]];
        return ;
    }
    int mid = (l + r) >> 1;
    build(p << 1,l,mid);
    build(p << 1 | 1,mid + 1,r);
    tree[p].minn = min(tree[p << 1].minn,tree[p << 1 | 1].minn);
    return ;
}

int query(int p,int x,int y) {
    if (tree[p].l >= x && tree[p].r <= y) {
        return tree[p].minn;
    }
    int mid = (tree[p].l + tree[p].r) >> 1,ans = INF;
    if (x <= mid) ans = min(ans,query(p << 1,x,y));
    if (y > mid) ans = min(ans,query(p << 1 | 1,x,y));
    return ans;
}

int qmin(int x,int y) {
    int ans = INF;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) {
            std::swap(x,y);
        }
        ans = min(ans,query(1,dfn[top[x]],dfn[x]));
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) std::swap(x,y);
    ans = min(ans,query(1,dfn[x] + 1,dfn[y]));
    return ans;
}

signed main() {
    Kruskal();
    //a[s] = INF;
    dfs1(s,0),dfs2(s,0),build(1,1,n);
    a[s] = INF;
    int T;read(T);
    while (T--) {
        int x,y;read(x,y);
        //printf("%d %d\n",x,y);
        if (find(x) != find(y)) {puts("-1");continue;}
        int tmp = qmin(x,y);
        printf("%d\n",tmp);
    }
    return 0;
}

其AC截图：

hack数据：

6 4
1 2 1
3 2 3
5 4 2
5 6 3
1
4 6