求树的重心模版题，$O(N)$为何网络上都说$O(nlogn)$或者$O(n^2)$

明明每个点访问一次，每条边访问一次，$O(n+n-1)$也就是$O(n)$。

代码来啦：

# include <stdio.h>
# include <vector>
using namespace std;

int n,size[100010];
vector<int> G[100010];
int asize,s;

void dfs(int x,int father) {
	size[x]=0;
	int balance=0;
	
	for (int i=0;i<G[x].size();++i) {
		int to=G[x][i];
		if(to==father) continue;
		dfs(to,x);
		size[x]+=size[to]+1;
		balance=max(balance,size[to]+1);
	}
	balance=max(balance,n-size[x]-1);
	if(balance<asize || (balance==asize && x<s)) {
		asize=balance;
		s=x;
	} 
}

int LBW;

int main() {
	scanf("%d",&LBW);
	while(LBW--) {
		scanf("%d",&n);
		for (int i=0;i<=n;++i) {
			G[i].clear();
			size[i]=0;
		}
		for (int i=1,a,b;i<n;++i) {
			scanf("%d%d",&a,&b);
			G[a].push_back(b);
			G[b].push_back(a);
		}
		asize=(1<<30);
		dfs(1,0);
		printf("%d %d\n",s,asize);
	}
	return 0;
}