写这个题的时候，其实已经手撸出LCA——树链剖分算法，
下面给出一段我的LCAn模板，说真的真的很好写不能更好写了，大家可以看看别的算法再来看我的实现，个人觉得写的还不错（一定要先有了解不然可能看不懂）
int dis[maxn], htop[maxn], sz[maxn], dep[maxn], hson[maxn], dist[maxn], fa[maxn];//sz[],当前节点孩子数目,htop[]当前节点所处重链,dep[]当前节点的深度,hson[]是这个节点的孩子中sz[]数组最大的节点,dist[]是从此节点到根的距离//fa[]他爹void dfs1(int u){ sz[u] = 1; for(int i = begin[u]; i; i = next[i]) if(to[i] != fa[u]){ int v = to[i]; fa[v] = u; dep[v] = dep[u] + 1; dis[v] = dis[u] + w[i]; dfs1(v); if(sz[v] > sz[hson[u]])hson[u] = v; sz[u] += sz[v]; }}void dfs2(int u, int v){ htop[u] = v; for(int i = begin[u]; i; i = next[i]){ int j = to[i]; if(htop[j])continue; if(hson[u] == j)dfs2(j, v); else dfs2(j, j); }}int lca(int a,int b){ while(htop[a] != htop[b]){ if(dep[htop[a]] < dep[htop[b]]){int t;t=a;a=b;b=t;} a=fa[htop[a]]; } return dep[a] < dep[b]?a : b;}这是模板，虽然下面的实现用不到这么多，但我还是写上吧；大家可以做参考，再写一个博客太累了。。。。。 接着到本题，其实很好理解，就是先用最大生成树，什么？怎么求->直接sort贪心拿最大值，所求的路径必定是最大生成树上的一条，否则不符合最大生成树定义
写这个博客主要是犯了很都比的错误，邻接表写错一个字母啊，sort排边写成n点的个数吐了；
还有就是开始写的时候写到查找的时候，发现顺序被打乱离线不好求，于是想参考网上的代码；
但是居然没有一个人写tarjan
#include#include #include #define N 40010#define M 100010 using namespace std;int n, m;int start[N], nxt[N], to[N], ee, f[N];int dep[N], dist[N],fa[N],w[N];struct truck{ int x,y,w;}e[M];bool cmp(truck a, truck b){return a.w>b.w;}void read(int &x){ char c=getchar(); x=0; while(c<'0' || c>'9')c=getchar(); while(c>='0' && c<= '9'){ x=x*10+c-'0'; c=getchar(); }}bool vis[N];void dfs(int u){ vis[u]=true; for(int i = start[u]; i; i=nxt[i]) if(!vis[to[i]]) { fa[to[i]]=u; dist[to[i]]=w[i]; dep[to[i]]=dep[u] + 1; dfs(to[i]); }}int check(int t1,int t2){ int mn1 = 0x7f7f7f7f, mn2 = 0x7f7f7f7f; if(dep[t1] < dep[t2]) swap(t1, t2); while(dep[t1] > dep[t2]) { mn1=min(mn1, dist[t1]); t1=fa[t1]; } while(t1!=t2) { mn1=min(mn1, dist[t1]); t1=fa[t1]; mn2=min(mn2, dist[t2]); t2=fa[t2]; } return min(mn1, mn2);}void add(int x, int y,int z){ to[++ee]=y; nxt[ee]=start[x]; start[x]=ee; w[ee]=z;}int find(int x){ if(f[x]!=x)return f[x]=find(f[x]); return f[x];}int main(){ read(n);read(m); for(int i=1; i<=m; ++i)read(e[i].x),read(e[i].y),read(e[i].w); for(int i=1; i<=n; ++i)f[i]=i; sort(e+1,e+m+1,cmp); int tot=0; for(int i=1; i<=m; ++i){ int a=find(e[i].x), b=find(e[i].y); if(a!=b){ f[a]=b; add(e[i].x,e[i].y,e[i].w); add(e[i].y,e[i].x,e[i].w); tot ++; if(tot==n-1)break; } } for(int i=1; i<=n; ++i)if(!vis[i])dfs(i); int q, x, y; read(q); for(int i=1; i<=q; ++i){ read(x);read(y); if(find(x)!=find(y)){puts("-1");continue;} printf("%d\n",check(x,y)); } return 0;}/*4 31 2 42 3 33 1 131 31 41 3*/