给出一棵树，有若干次询问，每次询问距两个点u, v距离相等的点的个数。
情况还挺多的，少侠不妨去看官方题解。^_^
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 using namespace std; 7 8 const int maxn = 100000 + 10; 9 10 int n, Q; 11 vector<int> G[maxn]; 12 13 int L[maxn]; 14 int fa[maxn]; 15 int sz[maxn]; 16 17 void dfs(int u) 18 { 19 sz[u] = 1; 20 for(int i = 0; i < G[u].size(); i++) 21 { 22 int v = G[u][i]; 23 if(v == fa[u]) continue; 24 fa[v] = u; 25 L[v] = L[u] + 1; 26 dfs(v); 27 sz[u] += sz[v]; 28 } 29 } 30 31 const int logmaxn = 20; 32 int anc[maxn][logmaxn]; 33 34 int ancestor(int a, int x) 35 { 36 if(!x) return a; 37 for(int i = 0; (1 << i) <= x; i++) 38 if(x & (1 << i)) a = anc[a][i]; 39 40 return a; 41 } 42 43 int LCA(int p, int q) 44 { 45 if(L[p] < L[q]) swap(p, q); 46 int log; 47 for(log = 1; (1 << log) <= L[p]; log++); log--; 48 for(int i = log; i >= 0; i--) 49 if(L[p] - (1 << i) >= L[q]) p = anc[p][i]; 50 if(p == q) return p; 51 for(int i = log; i >= 0; i--) 52 if(anc[p][i] && anc[p][i] != anc[q][i]) 53 p = anc[p][i], q = anc[q][i]; 54 return fa[p]; 55 } 56 57 int main() 58 { 59 //freopen("in.txt", "r", stdin); 60 61 scanf("%d", &n); 62 for(int i = 1; i < n; i++) 63 { 64 int u, v; scanf("%d%d", &u, &v); 65 G[u].push_back(v); 66 G[v].push_back(u); 67 } 68 69 dfs(1); 70 71 for(int i = 1; i <= n; i++) anc[i][0] = fa[i]; 72 for(int j = 1; (1 << j) < n; j++) 73 for(int i = 1; i <= n; i++) if(anc[i][j-1]) 74 anc[i][j] = anc[anc[i][j-1]][j-1]; 75 76 scanf("%d", &Q); 77 while(Q--) 78 { 79 int u, v; scanf("%d%d", &u, &v); 80 81 if(u == v) { printf("%d\n", n); continue; } 82 83 int l = LCA(u, v); 84 85 if((L[u] + L[v] - L[l] * 2) & 1) { puts("0"); continue; } 86 87 if(L[u] == L[v]) 88 { 89 int t = L[u] - L[l]; 90 int uu = ancestor(u, t - 1), vv = ancestor(v, t - 1); 91 printf("%d\n", n - sz[uu] - sz[vv]); 92 continue; 93 } 94 95 if(L[u] < L[v]) swap(u, v); 96 int t = L[u] + L[v] - L[l] * 2; 97 int p1 = ancestor(u, t / 2); 98 int p2 = ancestor(u, t / 2 - 1); 99 printf("%d\n", sz[p1] - sz[p2]); 100 } 101 102 return 0; 103 }