POJ 1655 求树的重心

tonyfang posted @ 2015年10月13日 21:29 in 随笔 with tags c++ OI , 1165 阅读

求树的重心模版题,$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;
}
jnanabhumiap.in 说:
2024年1月18日 16:50

JNANABHUMI AP provides all latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources full information on each topic which can be accessed through Internet. To ensure that every readers get’s what important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who have passion to provide engaging content which is accurate, interesting and worthy to read. We are mope like a web community where you can find different information’s, resources, topics on day to day incidents or news. We provide you the finest of web content on each and every topics possible with help of editorial and content team.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter