一眼看上去没什么思路，手摸一下样例，发现有不同性质的点对求解想法很不一样，考虑先分类讨论看看。
从简单的约束到强的约束分类讨论，这样更可做，也更好讨论，
比如首先我就想到两点是否重合，然后所求点一定要到两点的距离相等，我就想到路径长度的奇偶性，接着就考虑复杂的深度关系 ......
对于当前点对 (u,v)，
-
如果 u = v，则结果就是 n；
-
如果 u ≠ v
-
如果 u -> v 的简单路径长度为奇数，则结果为 0；
-
如果 u -> v 的简单路径长度为偶数
- 如果 \(dep[u] = dep[v]\)，可以发现路径上到 lca 肯定是符合要求的中点 mid，再往以 lca 这颗子树往外走就步步重合了，也就是说都成立，如果 lca 子树中到 u、v 的两颗子树的根节点分别为 fu、fv，则有：
-
-
-
- 如果 \(dep[u] \not = dep[v]\)，假设令 \(dep[u] > dep[v]\)，肯定还是要找路径上的中点 mid，但就一定不是 lca 了，但一定在较深的那颗子树里，所以还得从 u 往上跳一半的距离到 mid，显然满足的点肯定在 mid 延伸的子树上，且不是 u、v 所在的子树，这里只用考虑减掉 u 所在的子树大小就可以了，因为 v 肯定在 mid 往上走的路上，即：\[size[mid] - size[fu] \]
-
一开始实现后两部分讨论，我只用了普通的暴力上跳，\(O(mn)\) 的复杂度就 T 了（太投入了，我就老是会把想到脑边的做法先实现了再说）
code
#include <bits/stdc++.h>
#define re register int
using namespace std;
const int N = 1e5 + 10, logN = 50;
struct edge
{
int to, next;
}e[N << 1];
int top, h[N], dep[N], f[N][logN], size[N];
int n, m;
inline void add(int x, int y)
{
e[++ top] = (edge){y, h[x]};
h[x] = top;
}
void dfs(int u, int fa)
{
dep[u] = dep[fa] + 1;
f[u][0] = fa;
for (re i = 1; i <= log2(n); i ++)
f[u][i] = f[f[u][i - 1]][i - 1];
for (re i = h[u]; i; i = e[i].next)
{
int v = e[i].to;
if (v == fa) continue;
dfs(v, u);
size[u] += size[v];
}
}
inline int lca(int u, int v)
{
if (dep[u] < dep[v]) swap(u, v);
for (re i = log2(n); i >= 0; i --)
if (dep[f[u][i]] >= dep[v]) u = f[u][i];
if (u == v) return u;
for (re i = log2(n); i >= 0; i --)
if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
return f[u][0];
}
inline int work(int u, int v, int p)
{
if (u == v) return n;
int dist = dep[u] + dep[v] - 2 * dep[p];
if (dist % 2) return 0;
if (dep[u] == dep[v])
{
// return size[1] - size[p] + 1; 当 p = 1 时不成立
int fu = u, fv = v, du, dv;
du = dv = dist / 2 - 1;
while (du)
{
fu = f[fu][0];
du --;
}
while (dv)
{
fv = f[fv][0];
dv --;
}
return size[1] - size[fu] - size[fv];
}
else
{
if (dep[u] < dep[v]) swap(u, v);
int fu = u, mid;
dist = dist / 2 - 1;
while (dist)
{
fu = f[fu][0];
dist --;
}
mid = f[fu][0];
return size[mid] - size[fu];
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (re i = 1; i < n; i ++)
{
int x, y; cin >> x >> y;
add(x, y); add(y, x);
}
for (re i = 1; i <= n; i ++) size[i] = 1;
dfs(1, 0);
cin >> m;
while (m --)
{
int x, y; cin >> x >> y;
cout << work(x, y, lca(x, y)) << '\n';
}
return 0;
}
所以显然是要倍增上跳就可以了。\(O(m\log n)\)
#include <bits/stdc++.h>
#define re register int
using namespace std;
const int N = 1e5 + 10, logN = 50;
struct edge
{
int to, next;
}e[N << 1];
int top, h[N], dep[N], f[N][logN], size[N];
int n, m;
inline void add(int x, int y)
{
e[++ top] = (edge){y, h[x]};
h[x] = top;
}
void dfs(int u, int fa)
{
dep[u] = dep[fa] + 1;
f[u][0] = fa;
for (re i = 1; i <= log2(n); i ++)
f[u][i] = f[f[u][i - 1]][i - 1];
for (re i = h[u]; i; i = e[i].next)
{
int v = e[i].to;
if (v == fa) continue;
dfs(v, u);
size[u] += size[v];
}
}
inline int lca(int u, int v, int type)
{
if (dep[u] < dep[v]) swap(u, v);
for (re i = log2(n); i >= 0; i --)
if (dep[f[u][i]] >= dep[v]) u = f[u][i];
if (u == v) return u;
for (re i = log2(n); i >= 0; i --)
if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
if (!type) return f[u][0];
else return size[1] - size[u] - size[v];
}
inline int work(int u, int v, int p)
{
if (u == v) return n;
int dist = dep[u] + dep[v] - 2 * dep[p];
if (dist % 2) return 0;
if (dep[u] == dep[v])
{
// return size[1] - size[p] + 1; 当 p = 1 时不成立
return lca(u, v, 1);
}
else
{
if (dep[u] < dep[v]) swap(u, v);
int step = dist / 2;
int cnt = size[u];
for(int i = log2(n); i >= 0; i--)
if(step - (1 << i) > 0)
{
u = f[u][i];
cnt += size[u] - cnt;
step -= (1 << i);
}
u = f[u][0];
return size[u] - cnt;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (re i = 1; i < n; i ++)
{
int x, y; cin >> x >> y;
add(x, y); add(y, x);
}
for (re i = 1; i <= n; i ++) size[i] = 1;
dfs(1, 0);
cin >> m;
while (m --)
{
int x, y; cin >> x >> y;
cout << work(x, y, lca(x, y, 0)) << '\n';
}
return 0;
}