https://www.luogu.com.cn/record/87494950

#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 5;
struct edge {
	int to, next;
} e[N];
int T, f[N], siz[N], head[N], cnt, ans, n, u, v;
int find(int x) {
	return f[x] == x ? x : f[x];
}
void unionn(int x, int y) {
	int fx = find(x), fy = find(y);
	siz[fx] += siz[fy], f[fy] = fx;
}
void add(int u, int v) {
	e[++ cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T --) {
		cin >> n, ans = cnt = 0;
		for (int i = 1; i <= n; i ++)
			f[i] = i, siz[i] = 1, head[i] = 0;
		for (int i = 1; i < n; i ++)
			cin >> u >> v, add(max(u, v), min(u, v));
		for (int u = 1; u <= n; u ++) {
			int qwq = 0;
			for (int i = head[u]; i; i = e[i].next) {
				int v = e[i].to, fv = find(v);
				if (siz[fv] >= 1) qwq ++;
				unionn(u, v);
			}
			if (qwq >= 2) ans ++, siz[find(u)] -= 3;
		}
		cout << ans << '\n';
	}
	return 0;
}

捞：

https://www.luogu.com.cn/discuss/498895