倍增法求 LCA

倍增算法可以在线求树上两个点的LCA，时间复杂度为nlogn

预处理：通过dfs遍历，记录每个节点到根节点的距离dist[u]，深度d[u]
并求出树上每个节点i的2^j祖先f[i][j]

求最近公共祖先，根据两个节点的的深度，如不同，向上调整深度大的节点，使得两个节点在同一层上，如果正好是祖先结束，否则，将连个节点同时上移，查询最近公共祖先。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

struct node {
     node *next;
     int where, cost;
} *first[100001], a[200001];
int n, m, f[100001][21], l, dist[100001], D[100001], c[100001];

inline void makelist(int x, int y, int z) {
     a[++l].where = y; a[l].cost = z;
     a[l].next = first[x]; first[x] = &a[l];
}

int lca(int x, int y) {
     if (D[x] < D[y]) swap(x, y);
     int will = D[x] - D[y];
     for (int step = 0; will; will >>= 1, ++step)
          if (will & 1) x = f[x][step]; //移到同一层
     if (x == y) return x;
     for (int i = 20; i >= 0; --i) //这里 i 一定要 >=0 ,而不是>=1
          if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
     return f[x][0];
}

int main() {
     //freopen("lca.in", "r", stdin);
     //freopen("tree.out", "w", stdout);
     scanf("%d%d", &n, &m);
     memset(first, 0, sizeof(first)); l = 0;
     for (int i = 1; i < n; i++) {
          int x, y, z;
          scanf("%d%d%d", &x, &y, &z);
          makelist(x, y, z);
          makelist(y, x, z);
     }
     memset(f, 0, sizeof(f));
     memset(dist, 255, sizeof(dist));
     dist[1] = 0; c[1] = 1; D[1] = 0;
     for (int k = 1, l = 1; l <= k; l++) {//预处理出深度和f[i][j]
          int m = c[l];
          for (node *x = first[m]; x; x = x->next)
               if (dist[x->where] == -1) {
                    D[x->where] = D[m] + 1;
                    dist[x->where] = dist[m] + x->cost;
                    f[x->where][0] = m;
                    c[++k] = x->where;
               }
     }
     for (int i = 1; i <= 20; i++) 
          for (int j = 1; j <= n; j++)
               if (f[j][i - 1]) f[j][i] = f[f[j][i - 1]][i - 1];
     for (; m--; ) {
          int x, y;
          scanf("%d%d", &x, &y);
          cout<<dist[x]+dist[y]-2*dist[lca(x,y)]<<endl;
     }
     return 0;
}