[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;
}