When I did this question, I was too young, and I could only think of violence. In fact, if you know higher technology, this question can be AC ​​as long as you optimize the violence a little (I will not cry 75pts).

Without further ado, the idea of ​​violence is to enumerate each edge and find the center of gravity of the two subtrees.

The complexity of directly finding the center of gravity is \(O(n)\), and we consider optimizing it to \(O(\log{n})\).

We want to ask for the center of gravity of the subtree rooted at \(x\), first of all there is a lemma: this center of gravity must be on the heavy chain starting with \(x\) (here is the heavy chain in the light-heavy chain division chain). this is doing this question thought of.

This is actually quite understandable. If \(x\) is not the center of gravity, only its heavy son can be the center of gravity. Similarly, only the heavy son of its heavy son can be the center of gravity, so the center of gravity must be on the heavy chain.

There must be and at most two centers of gravity, so we find a deepest point\(y\) on the heavy chain such that \(n-sz[y] \le \frac{n}{2}\), this point has may be the center of gravity.

Another property of the center of gravity is that two points must be connected if they are the center of gravity. In this way, we only need to judge whether \(y\) and \(father[y]\) are the center.

How to find \(y\)? We found that doubling on the heavy chain is enough, similar to multiplying for lca.

How to maintain many arrays? Just change the root.

More properties about the center of gravity of trees

#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('\n');
}
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;
}