首先 \(n\) 为奇数所以只有一个重心 \(rt\)，以它为根，对于 \(x \neq rt\)，若 \(x\) 成为割掉某边后的重心，则这条边一定不在 \(x\) 子树内，设割掉后另一子树大小为 \(S\)，记 \(g_x = \max_{y \in son_x} sz_y\)，则有两个限制：
\[2 \times (n - S - sz_x) \le n - S
\]
\[2 \times g_x \le n - S
\]
得到：
\[n - 2sz_x \le S \le n - 2g_x
\]
且要求边不在 \(x\) 子树内，数据结构维护即可。
\(x = rt\) 可以在 dfs 途中处理。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 3e5 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {#ifdef ONLINE_JUDGEreturn ;#endifcout << arg << ' ';dbg(args...);
}
struct Query {int t, l, r;
};
int T, n, cg, sz[N], g[N], dfn[N], idx, m1, m2, in[N];
ll ans;
vector<int>e[N];
vector<Query>q[N];
struct Fenwick {int tr[N];#define lowbit(x) (x & -x)void clear() { for (int i = 1; i <= n; i++) tr[i] = 0; }void add(int x, int v) {if (!x) return ;while (x <= n) {tr[x] += v;x += lowbit(x);}}int qry(int x) {if (x < 0) return 0;int res = 0;while (x) {res += tr[x];x -= lowbit(x);}return res;}int ask(int l, int r) {if (l > r) return 0;return qry(r) - qry(l - 1);}
} t1, t2;
inline void dfs1(int u, int fa) {sz[u] = 1; g[u] = 0;dfn[u] = ++idx;for (auto v : e[u]) if (v != fa) {dfs1(v, u);sz[u] += sz[v];g[u] = max(g[u], sz[v]);}if (!cg && max(g[u], n - sz[u]) * 2 <= n) cg = u;
}
inline void dfs2(int u, int fa) {t1.add(sz[fa], -1);t1.add(n - sz[u], 1);if (u != cg) {int l = n - sz[u] * 2, r = n - g[u] * 2;ans += (ll)u * (t1.ask(l, r) + t2.ask(l, r));if (in[fa]) in[u] = 1;if (in[u]) ans += cg * (sz[u] <= n - sz[m2] * 2);else ans += cg * (sz[u] <= n - sz[m1] * 2);}t2.add(sz[u], 1);for (auto v : e[u]) if (v != fa) {dfs2(v, u);}t1.add(sz[fa], 1);t1.add(n - sz[u], -1);if (u != cg) {int l = n - sz[u] * 2, r = n - g[u] * 2;ans -= (ll)u * t2.ask(l, r);}
}
// 这里有个猎奇的点，就是 cg 为根的时候本来给 0 加一是会出问题的，但是这里由于 sz[0] = 0 恰好抵消了，当然我的意思是 xht 的写法是对的，因为 BIT 里给 x++ 了，但是不加还是会似
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> T;while (T--) {ans = 0;cin >> n;cg = m1 = m2 = 0;t1.clear(); t2.clear();for (int i = 1; i <= n; i++) e[i].clear(), q[i].clear(), in[i] = 0;for (int i = 1, u, v; i < n; i++) {cin >> u >> v;e[u].push_back(v); e[v].push_back(u);}dfs1(1, 0);idx = 0;dfs1(cg, 0);for (auto v : e[cg]) {if (sz[v] > sz[m1]) m2 = m1, m1 = v;else if (sz[v] > sz[m2]) m2 = v;}in[m1] = 1;for (int i = 1; i <= n; i++) t1.add(sz[i], 1);dfs2(cg, 0);cout << ans << '\n';}return 0;
}