转载一个大佬的题解：
下面谈谈我的感悟：
当然写代码也是写的很艰辛：
我力劝C++的同胞们，这题卡常数，Dfs党会吃亏，比如这里这个UOJ的数据
我们可以使用Bfs和尽量避免写Dfs,不然会Tle的
以下代码实测极端数据约900ms，正所谓卡常数，如果把一开始的dfs改为bfs可能会更快……（博主很懒，不改了）
总结一下大佬的题解：
1. Dfs或Bfs构建树，然后记录下各种信息，现在主要是以下几点：
1）子节点 son[rt] vector <int>
2）深度 deep[rt] int
3）到根节点的距离 dis[rt] int
4）到父亲节点的距离 fadis[rt] int
5）父亲 father[rt] int
2. LCA的预处理，处理出F[rt][i],表示节点rt的第2i个祖先（即节点rt的祖先中与之深度相差rt的祖先） // F[rt][i] 在代码中写成 Anst[rt][i]
转移表达式为：F[rt][i]=F[F[rt][i-1]][i-1] 应该都能够理解
3. 求取LCA: 这里用的倍增的方法，虽然比离线算法LCA_Tarjan慢一个log，但是倍增是一个好东西，不妨去练练。这样思考：对于两个深度为d的节点a和b，使得int i=log2(d),那么就可以倍增：对于节点a和b，如果他们的第2i个祖先是相同的，那么他们在网上的祖先也一定是相同的 ，那么我们就对于不改变a和b的值，而使i=i-1；如果他们的第2i个祖先不同，那么他们往下走的祖先也是不同的，于是就可以确定他们的最近公共祖先一定是在第2i个祖先上面的，那么我们就可以安心的把a和b的值更新乘F[a][i]和F[b][i](a=F[a][i],b=F[b][i])。直到i为0位置，无法再做了。于是，a和b的最近公共祖先就是a和b的父亲，即F[a][0]或F[b][0](相等的)。于是剩下的只是把a和b调到同一深度这点事情了。设b为深度更大的那个，设deep[x]为x的深度，那么把b移上去，就是求b个第(deep[b]-deep[a])个祖先，也是倍增可以解决的。
至于LCA_Tarjan，可以自己学啊！这里就不多说了。
3.二分答案：不用说了吧，就是一个基本的二分
4.check(答案):这个在大佬的题解里面写的比较详细，可以看他的~
#pragma comment(linker, "/STACK:10240000,10240000")
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;
const int N=+,M=N*,Inf=N*;
void read(int &x){
x=;
char ch=getchar();
while (!(''<=ch&&ch<=''))
ch=getchar();
while (''<=ch&&ch<=''){
x=x*+ch-;
ch=getchar();
}
}
struct Edge{
int cnt,y[M],z[M],nxt[M],fst[N];
void set(){
cnt=;
memset(y,,sizeof y);
memset(z,,sizeof z);
memset(nxt,,sizeof nxt);
memset(fst,,sizeof fst);
}
void add(int a,int b,int c){
cnt++;
y[cnt]=b,z[cnt]=c;
nxt[cnt]=fst[a],fst[a]=cnt;
}
}e;
int n,m;
vector <int> Tree[N];
int father[N],son[N],deep[N],dis[N],fadis[N],bh[N],bhtot;
int Anst[N][];//Ancestor
struct Query{
int x,y,LCA,cost;
}q[N];
int Nextsum[N];
void Build_Tree(int prev,int rt){
bh[++bhtot]=rt;
Tree[rt].clear();
deep[rt]=deep[prev]+;
son[rt]=;
father[rt]=prev;
for (int i=e.fst[rt];i;i=e.nxt[i])
if (e.y[i]!=prev){
son[rt]++,Tree[rt].push_back(e.y[i]);
fadis[e.y[i]]=e.z[i];
dis[e.y[i]]=dis[rt]+e.z[i];
Build_Tree(rt,e.y[i]);
}
}
void LCA_Prepare(){
memset(Anst,,sizeof Anst);
for (int i=;i<=n;i++){
int rt=bh[i];
Anst[rt][]=father[rt];
for (int i=;(<<i)<=deep[rt];i++)
Anst[rt][i]=Anst[Anst[rt][i-]][i-];
}
}
int LCA(int a,int b){
if (deep[a]>deep[b])
swap(a,b);
for (int i=deep[b]-deep[a],j=;i>;i>>=,j++)
if (i&)
b=Anst[b][j];
if (a==b)
return a;
int k;
for (k=;(<<k)<=deep[a];k++);
for (;k>=;k--)
if ((<<k)<=deep[a]&&Anst[a][k]!=Anst[b][k])
a=Anst[a][k],b=Anst[b][k];
return Anst[a][];
}
bool check(int t){
int total=,Maxcost=,Maxcut=;
memset(Nextsum,,sizeof Nextsum);
for (int i=;i<=m;i++)
if (q[i].cost>t){
Maxcost=max(Maxcost,q[i].cost-t);
total++;
Nextsum[q[i].x]++;
Nextsum[q[i].y]++;
Nextsum[q[i].LCA]-=;
}
for (int i=n;i>=;i--)
Nextsum[father[bh[i]]]+=Nextsum[bh[i]];
for (int i=;i<=n;i++)
if (Nextsum[i]==total)
Maxcut=max(Maxcut,fadis[i]);
return Maxcost<=Maxcut;
}
int main(){
scanf("%d%d",&n,&m);
e.set();
for (int i=;i<n;i++){
int a,b,c;
read(a),read(b),read(c);
e.add(a,b,c);
e.add(b,a,c);
}
bhtot=;
deep[]=-,dis[]=fadis[]=;
Build_Tree(,);
LCA_Prepare();
for (int i=;i<=m;i++){
read(q[i].x),read(q[i].y);
q[i].LCA=LCA(q[i].x,q[i].y);
q[i].cost=dis[q[i].x]+dis[q[i].y]-dis[q[i].LCA]*;
}
int le=,ri=Inf,mid,ans=;
while (le<=ri){
mid=(le+ri)>>;
if (check(mid))
ri=mid-,ans=mid;
else
le=mid+;
}
printf("%d",ans);
return ;
}
代码