A and B and Lecture Rooms CodeForces - 519E(LCA倍增，思维)

本文主要是介绍A and B and Lecture Rooms CodeForces - 519E(LCA倍增，思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

给定一棵树，然后q个询问，距离两个点距离相等点的个数。

思路

先用LCA求出两个点的最近公共祖先，然后判断距离，如果说两个点距离lca的距离和为奇数那么不存在距离相等的点，如果说距离为偶数，那么又可以分出两种情况，第一种情况是距离相等那么就是所有的点数量去掉包lca包含a，b子树的节点数。距离不相等，那么就是中点位置的子树节点数减去其包含深度大的那个结点子树。

代码

#include <bits/stdc++.h>
using namespace std;const int maxn = 1e5 + 10;
int n, m;
int f[maxn][20], sz[maxn], dep[maxn];
int head[maxn], to[maxn * 2], nxt[maxn * 2], tot;
void dfs(int u, int from) {sz[u] = 1;f[u][0] = from;for(int e = head[u]; ~e; e = nxt[e]) {int v = to[e];if(v == from) continue;dep[v] = dep[u] + 1;dfs(v, u);sz[u] += sz[v];}
}
void init() {dep[1] = 1;dfs(1, 0);for(int j = 1; (1 << j) <= maxn; j++ ) {for(int i = 1; i <= n; i++) {f[i][j] = f[f[i][j-1]][j-1];}}
}void addedge(int u, int v) {to[tot] = v, nxt[tot] = head[u], head[u] = tot++;
}int LCA(int a, int b) {if(dep[a] < dep[b]) swap(a, b);int d = dep[a] - dep[b];for(int i = 19; i >= 0; i--) {if((1 << i) & d) a = f[a][i];}if(a!=b) {for(int i = 19; i >= 0; i--) {if(f[a][i] != f[b][i]) {a = f[a][i];b = f[b][i];}}a = f[a][0];}return a;
}int Jump(int u, int lev) {for(int i = 19; i >= 0; i--) {if((1 << i) & lev) u = f[u][i];}return u;
}int sol(int a, int b) {if(a == b) return sz[1];if(dep[a] < dep[b]) swap(a, b);int lca = LCA(a, b);int da = dep[a] - dep[lca];int db = dep[b] - dep[lca];int dis = da + db;if(dis & 1) return 0;if(da == db) return sz[1] - sz[Jump(a, da - 1)] - sz[Jump(b, db - 1)];int midpos = Jump(a, dis / 2);return sz[midpos] - sz[Jump(a, dis/2-1)]; 
}int main() {memset(head, -1, sizeof(head)); tot = 0;cin >> n;for(int i = 0; i < n - 1; i++) {int u, v; cin >> u >> v;addedge(u, v); addedge(v, u);}init();int q;cin >> q;while(q--) {int a, b;cin >> a >> b;cout << sol(a, b) << endl;}return 0;
}