[TIOJ] 1947. 小向的試煉 1-3:森林(Forest)

題目連結:http://tioj.infor.org/problems/1947
裸樹重心題,而要怎麼找樹重心呢?直接DFS吧,在DFS時你就知道他小孩的子樹大小,而他祖先那塊子樹不難發現就是點數減下子樹的數量,然後就記個最小值大概這樣吧
#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long lld;
using std::max;
using std::min;
using std::vector;

lld n,m=2147483647999;

vector<int> graph[1000010];

inline lld DFS(int,int);

int main(){
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	DFS(0,-1);
	printf("%lld",m);
	return 0;
}

inline lld DFS(int k,int f){
	lld size=1;
	lld sub=0;
	for(int i=0;i<graph[k].size();i++){
		if(graph[k][i] == f)continue;
		lld each=DFS(graph[k][i],k);
		sub=max(each, sub);
		size+=each;
	}
	m = min(m,max(sub,(n-size)));
	return size;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology