期待：按照部分分一步一步去想应该是不难出正解的，这题难点应该在于实现上。
看到题感觉不太好直接入手，于是先考虑特殊性质。特殊性质 A 的做法比较神秘，特殊性质 B 就是个骗分的，没啥启发性。
而特殊性质 C 是真正对正解有帮助的部分分。从链的角度考虑，可以把两个必经点 \(a, b\) 在链上标出来，然后很显然可以枚举 \(\bm{u, v}\) 之间的长度，根据 \(u, v\) 谁在左、谁在右分类讨论，算出 \(u, v\) 的取值区间，乘法原理计算即可。此处同样有一个简化计数流程的观察：大多数的移动方案都是成对出现的，也就是说大多数情况下我们只需要对正向走的方案计数一次，反向的不用算，直接将正向的答案乘 \(2\) 即可。
由特殊性质的做法，启发我们通过枚举 \(u, v\) 之间的距离 \(d\) 进行计数。考虑正解，这里着重对计数过程讲解：
因为是无根树，为了方便刻画，我们强制将 \(\bm a\) 钦定为树根。且在下文中，假设 \(u\) 的必经点为 \(b\)，\(v\) 的必经点为 \(a\)；\(u, v\) 最后的位置为 \(u', v'\)；\(c\) 表示同时为 \(b\) 的祖先和 \(a\) 的儿子的节点，\(T\) 表示原树删掉 \(c\) 的子树后剩下的树。
对 \(u, v\) 的方位进行讨论，并钦定向上走为正方向：
- \(u\) 在下，\(v\) 在上：对 \(u, v'\) 计数。
- 需要满足 \(dep_u\ge d\)，因为 \(v\) 一旦不是 \(u\) 的祖先了，则向上走会使得 \(v\) 一直无法与 \(a\) 重合。
- 需要满足 \(dep_u\ge dep_b\)，因为是向上走，\(u\) 想要和 \(b\) 重合就必须在 \(b\) 子树内。
- 需要满足 \(dep_{v'}\ge \max\{d - dep_b, 0\}\)。其中 \(\max\{d - dep_b, 0\}\) 的含义是当 \(v\) 与 \(a\) 重合时，\(u\) 与 \(b\) 重合所需的最少步数。这个限制是因为只有 \(u, v\) 都满足要求了才是一个合法的方案。
- \(u\) 在上，\(v\) 在下：对 \(u', v\) 计数。
- 需要满足 \(dep_v - d \ge dep_b\)。其中 \(dep_v - d = dep_u\)。因为只有 \(u\) 在 \(b\) 的子树内，向上走的时候才能有重合。
- 需要满足 \(dep_{u'}\ge d\)。因为当 \(v\) 与 \(a\) 重合时，\(u\) 会往 \(T\) 内延伸 \(d\) 的长度。
发现我们只需要用到 \(b\) 子树内、\(T\) 内的深度信息。于是可以分别对这两棵树做 DFS，然后把所有节点的深度扔进一个桶里，统计的时候运用前缀和、乘法原理计数即可。
发现还是过不了，手模第一个和第二个小样例可以发现两个 corner case：
- 当 \(a, b\) 相差为 \(1\) 的时候，会多一个方案：\((a, b)\to (b, a)\)。
- 当 \(a, b\) 相差大于等于 \(2\) 的时候，\((a, b)\) 可能被记录了两次，需要减掉一次。
判掉这两个 corner case 即可通过，时间复杂度 \(O(n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 100005;
int n, a, b, mxdep, father[N], dep[N], sz[N], tot[N], smtot[N];
vector<int> g[N];
ll ans;
void dfs1(int u, int fa) // 求深度、父节点、子树大小
{father[u] = fa;sz[u] = 1;for(auto v : g[u]){if(v == fa) continue;dep[v] = dep[u] + 1;dfs1(v, u);sz[u] += sz[v];}
}
void dfs2(int u, int fa) // 求 b 子树内的桶
{tot[dep[u]]++;for(auto v : g[u]){if(v == fa) continue;dfs2(v, u);}
}
void dfs3(int u, int ban) // 求 T 内的桶
{smtot[dep[u]]++;for(auto v : g[u]){if(v == father[u] || v == ban) continue;dfs3(v, ban);}
}
void solve()
{cin >> n >> a >> b;ans = 0;for(int i = 1; i <= n; i++)g[i].clear();for(int i = 1; i < n; i++){int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dep[a] = 0;memset(tot, 0, sizeof(tot));memset(smtot, 0, sizeof(smtot));dfs1(a, 0);dfs2(b, father[b]);int now = b;while(father[now] != a)now = father[now];dfs3(a, now);for(int i = 1; i <= n; i++){tot[i] += tot[i - 1];smtot[i] += smtot[i - 1];}for(int d = 0; d < n; d++){// u 下 v 上int xj = max(dep[b], d);int rj = max(0, d - dep[b]);ans += 2ll * (tot[n] - tot[xj - 1]) * (smtot[n] - (rj == 0 ? 0 : smtot[rj - 1]));// u 上 v 下if(d == 0) continue;xj = dep[b] + d;ans += 2ll * (tot[n] - tot[xj - 1]) * (smtot[n] - (d == 0 ? 0 : smtot[d - 1]));}if(dep[b] == 1) ans++;if(dep[b] >= 2) ans--;cout << ans << "\n";
}
int main()
{// freopen("counting5.in", "r", stdin);// freopen("sample.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--) solve();return 0;
}