模板及讲解 倍增思想，维护 deep[i],pre[i][j] 为点 i 的深度和点i的 2j 个祖先结点 然后对于每一对 x,y 求 LCA(x,y) ，先把深的结点提上来和浅结点深度相同，如果此时 x,y 都相同，说明 x,y 在同侧，输出 x,y 任意一个即可，否则再一起提上来直到两点相等，输出 pre[x][0] 或者 pre[y][0]
跳的时候跳二进制，即 设 del=deep[b]−deep[a](deep[b]>=deep[a]) 如果 del=5 ， 二进制为 101 那么从左往右扫描，第 i 位为1的就跳 2i 个点 del=5 时，跳 22 和 20 即可
常见题型 1. LCA思想 Q：一棵树，询问一个路径u->v，先再路径上选取一个a1, 再在后面选取一个a2, 使得(a1-a2)最大 解：运用LCA(倍增)思想。 例题：poj 3728 2. 结合dfs序 Q：一棵树，有两种操作：1、求u, v路径上的权值和 2、修改一条边的权值 解：修改边权会使far数组改变，那么用数据结构维护far数组 例题：poj2763
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; #define ms(i,j) memset(i, j, sizeof i); const int MAXN = 40000 + 5, logs = 21; struct edge { int x, y, c; }ed[2*MAXN]; int en; int n, m; vector<int> G[MAXN]; int deep[MAXN], far[MAXN], pre[MAXN][logs+1]; //深度，距离根节点距离(权值和)，结点的2^i祖先 void dfs(int x, int p)//搜索一次初始化记录 { pre[x][0] = p; for (int i=1;i<=logs;i++) pre[x][i] = pre[pre[x][i-1]][i-1];//运用性质求2^i祖先 for (int i=0;i<G[x].size();i++)//向下搜索 { int v = ed[G[x][i]].y; if (v!=p) { deep[v] = deep[x] + 1; far[v] = far[x] + ed[G[x][i]].c; dfs(v,x); } } } int lca(int a, int b) { if (deep[a]>deep[b]) swap(a, b); for (int i=logs;i>=0;i--) if (deep[pre[b][i]]>=deep[a]) b = pre[b][i];//抬升到同一高度 //也可以 dep = deep[b] - deep[a]; if ((dep>>1)&1) if (a==b) return a;//如果在同侧 for (int i=logs;i>=0;i--) if (pre[a][i]!=pre[b][i]) a = pre[a][i], b = pre[b][i];//继续不断往上提 return pre[a][0];//最终答案是a或者b的父亲结点 } void addedge(int x, int y, int c) { en++; ed[en].x = x; ed[en].y = y; ed[en].c = c; G[x].push_back(en); en++; ed[en].x = y; ed[en].y = x; ed[en].c = c; G[y].push_back(en); } void init() { for (int i=1;i<=n;i++) G[i].clear(); en = 0; scanf("%d%d", &n, &m); for (int i=1;i<n;i++) { int x, y, c; scanf("%d%d%d", &x, &y, &c); addedge(x, y, c); } } void solve() { ms(pre, 0); ms(deep, 0); ms(far, 0); dfs(1, 0); for (int i=1;i<=m;i++) { int x, y; scanf("%d%d", &x, &y); printf("%d\n", far[x]+far[y]-2*far[lca(x,y)]); } } int main() { int t; scanf("%d", &t); while (t--) { init(); solve(); } return 0; }