当年我做这道题时还太嫩了，只能想到暴力。其实如果会了更高的科技这道题只要稍微对暴力优化一下就能AC（我也不会含泪75pts了）。
废话不说了，暴力的思路就是枚举每一条边然后求两个子树的重心。
直接求重心的复杂度是(O(n))的，我们考虑优化到(O(log{n}))。
我们想要求以(x)为根的子树的重心，首先有个引理：这个重心一定在以(x)开头的这条重链上（这里就是轻重链剖分中的重链）。这是在做这题时想到的。
这其实蛮好理解的，如果(x)不是重心，则只有其重儿子才有可能是重心，同理只有其重儿子的重儿子才有可能是重心，所以重心一定在重链上。
重心一定有且最多有两个，所以我们在重链上找一个最深的点(y)使得(n-sz[y] le frac{n}{2})，这个点有可能成为重心。
重心的另一个性质是如果两点是重心则其一定相连。这样我们只需判断(y)和(father[y])是不是中心即可。
怎么找到(y)？我们发现在重链上倍增就行，类似倍增求lca。
怎么维护众多数组？换根就行。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 300000;
template <typename T> void read(T &x) {
T f = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
x *= f;
}
template <typename T> void write(T x) {
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T> void print(T x) {
if (x < 0) putchar('-'), x = -x;
write(x);
putchar('
');
}
struct node{
int pre, to;
}edge[N << 1];
int head[N], tot;
int T;
int n;
int sz[N], son[N], g[N][21], father[N];
ll ans;
void init() {
for (int i = 1; i <= n; i++) head[i] = 0;
tot = ans = 0;
}
void add(int u, int v) {
edge[++tot] = node{head[u], v};
head[u] = tot;
}
void calc(int x) {
g[x][0] = son[x];
for (int i = 1; i <= 20; i++) g[x][i] = g[g[x][i - 1]][i - 1];
}
void dfs1(int x, int fa) {
sz[x] = 1;
son[x] = 0;
for (int i = head[x]; i; i = edge[i].pre) {
int y = edge[i].to;
if (y == fa) continue;
father[y] = x;
dfs1(y, x);
sz[x] += sz[y];
if (sz[y] > sz[son[x]]) son[x] = y;
}
calc(x);
}
int check(int x, int total) {
if (max(sz[son[x]], total - sz[x]) <= (total >> 1)) return 1;
return 0;
}
void get_ans(int x) {
int now = x;
for (int i = 20; i >= 0; i--) if (g[now][i] && sz[x] - sz[g[now][i]] <= (sz[x] >> 1)) now = g[now][i];
ans += check(now, sz[x]) * now + check(father[now], sz[x]) * father[now];
}
void change_root(int x, int y) {
sz[x] -= sz[y];
sz[y] += sz[x];
father[x] = y;
father[y] = 0;
if (son[x] == y) {
son[x] = 0;
for (int i = head[x]; i; i = edge[i].pre) {
int z = edge[i].to;
if (z == y) continue;
if (sz[z] > sz[son[x]]) son[x] = z;
}
calc(x);
}
if (sz[x] > sz[son[y]]) son[y] = x, calc(y);
}
void dfs2(int x, int fa) {
for (int i = head[x]; i; i = edge[i].pre) {
int y = edge[i].to;
if (y == fa) continue;
get_ans(y);
change_root(x, y);
get_ans(x);
dfs2(y, x);
change_root(y, x);
}
}
int main() {
read(T);
while (T--) {
read(n);
init();
for (int i = 1, u, v; i < n; i++) {
read(u); read(v);
add(u, v); add(v, u);
}
dfs1(1, 0);
dfs2(1, 0);
print(ans);
}
return 0;
}