NOIP2013货车运输 ，这道题很有价值。
很多题解都没有说清楚为什么要跑最大生成树，我这里会证明。
数据范围：n<=1e4,m<=5e4........
O（nlogn）的算法可以过，而且与公共祖先有关，所以用LCA。
算法思路：
为什么先跑一遍最大生成树？两点之间的道路的最小载重量一定是在树边上？
可以用反证法：
1
/ \
2 3
/
4
这是一个最大生成树，假设3--->4之间还有一条边权比4-->2-->1-->3中最小边权更大的边，我们以Kruskal算法为例：
3--->4为非树边，且在Kruskal算法的过程中，若3---->4这条边没有被选，有两种情况
1. 3--->4的边权比4--->2--->1--->3要小，这与我们假设的条件不符合，舍去此情况。
2. 3--->4这条边正准备被选的时候，发现3和4正好已经在一个集合中，才会是非树边，及1.2.3.4已经联通，那么肯定选了4-->2-->1-->3这些边，那么3-->4的边权一定比4-->2-->1-->3这些边的边权要小，与假设不符。
证毕。
代码：
void Kruskal(){ int tim=0; while(!q.empty()){ if(tim>=n-1)return; int r1=find(q.top().u),r2=find(q.top().v); if(r1!=r2){ tim++; col[q.top().u]=1; col[q.top().v]=1; fin[r1]=r2; add(q.top().u,q.top().v,q.top().w); add(q.top().v,q.top().u,q.top().w); } q.pop(); } }
DFS在预处理 Min的时候，Min[u][i]表示 第u个点到其第2^i个祖先之间的边权最小值.
代码：
void dfs(int pos,int fa){ dep[pos]=dep[fa]+1; f[pos][0]=fa; for(int i=1;(1<<i)<=dep[pos];i++){ f[pos][i]=f[f[pos][i-1]][i-1]; Min[pos][i]=min(Min[pos][i-1],Min[f[pos][i-1]][i-1]); } for(int i=head[pos];i;i=E[i].nxt) if(E[i].to!=fa){ Min[E[i].to][0]=E[i].dis; dfs(E[i].to,pos); } }
在这段代码中我犯的错误：
将Min[f[pos][i-1]][i-1]写成了Min[Min[pos][i-1]][i-1],第一维记录的是父亲的编号，怎么能是Min呢！
LCA代码：
int lca(int a,int b){ int minn=0x3f3f3f3f; if(dep[a]>dep[b]) swap(a,b); for(int i=20;i>=0;i--) if((dep[a]+(1<<i))<=dep[b]){ minn=min(minn,Min[b][i]);//跳到同一高度的时候需要更新。 b=f[b][i]; } if(a==b)return minn; for(int i=20;i>=0;i--){ if(f[a][i]==f[b][i]) continue; else { minn=min(minn,min(Min[a][i],Min[b][i]));//不能用LCA的父亲去更新Min a=f[a][i]; b=f[b][i]; } } return min(minn,min(Min[b][0],Min[a][0]));而且我们刚刚跳的时候，是调到lca的儿子，
它有两个儿子，所以需要用两条边来更新Min。
}
不预处理，暴力找Min也可以过洛谷的数据。
思路：每次找父亲，更新minn，调到lca就停。
贴下代码：
int getans(int a,int b){ int LCA=lca(a,b); int minn=0x3f3f3f3f; for(int i=a;i<=n;i=f[i][0]){ if(i==LCA)break; minn=min(minn,Min[i][0]); } for(int i=b;i<=n;i=f[i][0]){ if(i==LCA)break; minn=min(minn,Min[i][0]); } return minn; }
数据比较水，两种找Minn的方法用时只差100+ms.
原文：https://www.cnblogs.com/sky-zxz/p/9738121.html