引入：
比如说要找树上任意两个点的路上的最大值。如果是一般的做法 会 接近o（n）的搜，从一个点搜到另一个点，但是如果询问多了复杂度就很高了。
然后我们会预处理。预处理是o（n²）的，询问是o（1）的，但是n大了，时间会超，内存也开不下。
这个时候就需要lca了。如果是倍增lca的话。处理是o（nlogn的），询问是o(logn）的，你发现什么东西都log一遍就很简单了。。。
lca：
先说下lca。为什么要用lca，打个比方，如果我们事先知道了一个点往上任何一个点是啥，并且到它的路径上的最大值也知道。当询问两个点时，只需要找到他们两往上第一个相同的点（即为lca），然后把他们两往上的值取个最大值，这就是我们的答案。但是这样处理的话，发现空间开不下，如果n大了不可能开一个n²的数组。这时我们需要倍增算法。
倍增：
如果我们提前知道了每个点往上2 ^k的点，那么一个点往上2 ^ （k + 1）的点，即为它往上2 ^ k的点再往上2 ^ k的点（相当于我们借助一个点往上2 ^ k的点为跳板，再往上跳2 ^ k，即可到达一个点往上2 ^ (k + 1)的点）这样每次寻找一个点往上任何高度的点变为了 log；
就这样维护一遍就可以求了
贴上自己yy的代码：
#include#include #include using namespace std;const int N = 4e4;const int M = 4e5;using namespace std;int h[N],cnt,gra[N][32],dep[N];int maxn[N][32],n,m;struct path{ int next,to; int dis;}e[M];void add(int u,int v,int dis){ e[++cnt].to = v; e[cnt].next = h[u]; e[cnt].dis = dis; h[u] = cnt;}void dfs(int u,int pre){ for(int i = h[u];i;i = e[i].next){ int v = e[i].to; if(v == pre)continue; gra[v][0] = u;//处理出每个点的直接父亲 maxn[v][0] = e[i].dis;//处理出每个点到直接父亲的距离 dep[v] = dep[u] + 1; dfs(v,u); }}int LCA(int x,int y){ if(dep[x] < dep[y])swap(x,y); int flag = false; int log; for(log = 1;(1 << log) <= dep[x];log++);log--; int ans = 0; for(int i = log;i >= 0;i--) if(dep[x] - (1 << i) >= dep[y]){ ans = max(ans,maxn[x][i]); x = gra[x][i]; }//把x向上移到和y相同高度 if(x == y)return ans;//如果y就是lca 直接跳出 for(int i = log;i >= 0;i--){ if(gra[x][i] && gra[y][i] != gra[x][i]){ ans = max(ans,maxn[x][i]);x = gra[x][i]; ans = max(ans,maxn[y][i]);y = gra[y][i]; } }//把x 和 y同时向上移，如果相同，即找到lca if(gra[x][0])ans = max(ans,maxn[x][0]); if(gra[y][0])ans = max(ans,maxn[y][0]); if(!gra[x][0] && x != y)return -1;//如果移到根节点且x ！= y即x，y不在一颗树上返回-1 return ans;}void getMap(){ scanf("%d %d",&m,&n); int a,b,z; for(int i = 1;i <= n;i++){ scanf("%d %d %d",&a,&b,&z); add(a,b,z); add(b,a,z); } for(int i = 1;i <= m;i++){ if(!dep[i]){ dep[i] = 1; dfs(i,-1); } } for(int j = 1;(1 << j) <= m;j++) for(int i = 1;i <= m;i++) if(gra[i][j - 1]){ int a = gra[i][j - 1]; gra[i][j] = gra[a][j - 1]; maxn[i][j] = max(maxn[i][j - 1],maxn[a][j - 1]); }//处理出每个点1 - 2^k的父亲，和路上最大边权；}int main(){ getMap(); return 0;}