今天拿了这道题目练练手，感觉自己代码能力又增强了不少；
我的思路跟别人可能不一样。
首先我们很容易就能看出，我们需要的边就是最小生成树算法kruskal算法求出来的边，其余的边都可以删掉，于是就有了这个kruskal选边建图的过程。
struct kruskalsolve{
int l,r,w;
}kr[maxm];
此处省略的内容接下来会有给出全部代码
int find(int x){
if(f[x] != x)f[x] = find(f[x]);
return f[x];
}
void kruskal_check(int m){
int cnte = ;
sort(kr+,kr+m+,cmp);
for(int i = ;i <= n;++i){
f[i] = i;
}
for(int i = ;i <= m;++i){
if(cnte == n-)break;
int s = find(kr[i].l);
int t = find(kr[i].r);
if(s != t){
f[s] = t;
e[++cnte][] = kr[i].l;
e[cnte][] = kr[i].r;
e[cnte][] = kr[i].w;
addedge(kr[i].l,kr[i].r);
addedge(kr[i].r,kr[i].l);
}
}
}
做到这里，有人可能觉得接下来一个LCA接着就可以AC了，不过蒟蒻认为这样做效率有点低，然后代码也不怎么好写，于是换成了树链剖分+线段树模板维护查询区间最大值的思路。（什么思路！！明明是套板子……这要解释的话就比较尴尬了）
这样的话效率就是O（nlogn）的总效率，感觉不错，但是就是代码量稍微有点大，请读者见谅。
建议大家还是先去学一下树链剖分的思路和板子，然后在看我的题解，毕竟光copy别人的，自己时间长了肯定忘，最好的还是自己懂了思路然后再自己手码出来。
废话不说了，上代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = ,maxm = ;
int n,m,q,s,t;
int id[maxn],top[maxn],son[maxn],fa[maxn],h[maxn],cnt,siz[maxn],dep[maxn],val[maxn],num,f[maxn];
struct kruskalsolve{
int l,r,w;
}kr[maxm];
struct edge{
int fr,to,next;
}edges[maxn<<];
struct segtree{
int l,r,val;
}tr[maxm<<];
int e[maxn][];
bool cmp(kruskalsolve a,kruskalsolve b){
return a.w < b.w;
}
void init(){
cnt = ;
memset(h,-,sizeof(h));
memset(dep,,sizeof(dep));
memset(siz,,sizeof(siz));
memset(fa,,sizeof(fa));
memset(id,,sizeof(id));
memset(edges,,sizeof(edge));
memset(val,,sizeof(val));
memset(e,,sizeof(e));
memset(top,,sizeof(top));
memset(tr,,sizeof(tr));
num = ;
}
void addedge(int u,int v){
edges[cnt].fr = u;edges[cnt].to = v;edges[cnt].next = h[u];
h[u] = cnt++;
}
int find(int x){
if(f[x] != x)f[x] = find(f[x]);
return f[x];
}
void kruskal_check(int m){
int cnte = ;
sort(kr+,kr+m+,cmp);
for(int i = ;i <= n;++i){
f[i] = i;
}
for(int i = ;i <= m;++i){
if(cnte == n-)break;
int s = find(kr[i].l);
int t = find(kr[i].r);
if(s != t){
f[s] = t;
e[++cnte][] = kr[i].l;
e[cnte][] = kr[i].r;
e[cnte][] = kr[i].w;
addedge(kr[i].l,kr[i].r);
addedge(kr[i].r,kr[i].l);
}
}
}
void dfs1(int now ,int father ,int d){
dep[now] = d;
fa[now] = father;
son[now] = ;
siz[now] = ;
for(int i = h[now];i != -;i = edges[i].next){
edge e1 = edges[i];
if(e1.to == father)continue;
dfs1(e1.to,now,d+);
siz[now] += siz[e1.to];
if(siz[son[now]] < siz[e1.to])son[now] = e1.to;
}
}
void getpos(int now,int tp){
id[now] = ++num;
top[now] = tp;
if(son[now])getpos(son[now],tp);
for(int i = h[now];i != -;i = edges[i].next){
edge e1 = edges[i];
if(e1.to == son[now] || e1.to == fa[now])continue;
getpos(e1.to,e1.to);
}
}
void push_up(int v){
tr[v].val = max(tr[v<<].val,tr[v<<|].val);
}
void build(int l,int r,int now){
tr[now].l = l;
tr[now].r = r;
if(l == r){
tr[now].val = val[l];
return;
}
int mid = (l + r) >> ;
build(l,mid,now<<);
build(mid+,r,now<<|);
push_up(now);
}
int query(int x,int l,int r){
if(l <= tr[x].l && r >= tr[x].r){
return tr[x].val;
}
int ans = ;
int mid = (tr[x].l + tr[x].r) >> ;
if(l <= mid)ans = max(ans,query(x<<,l,r));
if(r > mid)ans = max(ans,query(x<<|,l,r));
return ans;
}
int youth(int u,int v){
int ans = ;
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]])swap(u,v);
ans = max(ans,query(,id[top[u]],id[u]));
u = fa[top[u]];
}
if(u == v)return ans;
if(dep[u] > dep[v])swap(u,v);
ans = max(ans,query(,id[son[u]],id[v]));
return ans;
}
int main(){
init();
scanf("%d%d",&n,&m);
for(int i = ;i <= m;++i){
scanf("%d%d%d",&kr[i].l,&kr[i].r,&kr[i].w);
}
kruskal_check(m);
dfs1(,-,);
getpos(,);
for(int i = ;i < n;++i){
if(dep[e[i][]] < dep[e[i][]])swap(e[i][],e[i][]);
val[id[e[i][]]] = e[i][];
}
build(,n,);
scanf("%d",&q);
for(int i = ;i <= q;++i){
scanf("%d%d",&s,&t);
printf("%d\n",youth(s,t));
}
return ;
}
这次写的解题报告就到这里吧，以后会尽量去写。