水题。
直接倍增求lca。
x到y的距离为dis[x] + dis[y] - 2 * dis[lca(x, y)]
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define MAXN 20002 5 6 using namespace std; 7 8 int n, q, cnt; 9 int head[MAXN], to[MAXN], next[MAXN], val[MAXN], deep[MAXN], f[MAXN][21], dis[MAXN]; 10 11 inline void add(int x, int y, int z) 12 { 13 to[cnt] = y; 14 val[cnt] = z; 15 next[cnt] = head[x]; 16 head[x] = cnt++; 17 } 18 19 inline void dfs(int u) 20 { 21 int i, v; 22 deep[u] = deep[f[u][0]] + 1; 23 for(i = 0; f[u][i]; i++) f[u][i + 1] = f[f[u][i]][i]; 24 for(i = head[u]; i != -1; i = next[i]) 25 { 26 v = to[i]; 27 if(!deep[v]) 28 { 29 f[v][0] = u; 30 dis[v] = dis[u] + val[i]; 31 dfs(v); 32 } 33 } 34 } 35 36 inline int lca(int x, int y) 37 { 38 int i; 39 if(deep[x] < deep[y]) swap(x, y); 40 for(i = 20; i >= 0; i--) 41 if(deep[f[x][i]] >= deep[y]) 42 x = f[x][i]; 43 if(x == y) return x; 44 for(i = 20; i >= 0; i--) 45 if(f[x][i] != f[y][i]) 46 x = f[x][i], y = f[y][i]; 47 return f[x][0]; 48 } 49 50 int main() 51 { 52 int i, x, y, z; 53 scanf("%d %d", &n, &q); 54 memset(head, -1, sizeof(head)); 55 for(i = 1; i < n; i++) 56 { 57 scanf("%d %d %d", &x, &y, &z); 58 add(x, y, z); 59 add(y, x, z); 60 } 61 deep[1] = 1; 62 dfs(1); 63 for(i = 1; i <= q; i++) 64 { 65 scanf("%d %d", &x, &y); 66 printf("%d ", dis[x] + dis[y] - 2 * dis[lca(x, y)]); 67 } 68 return 0; 69 }