POJ 2378 Tree Cutting
問題
http://poj.org/problem?id=2378
解法
適当な頂点を選んで根にしてDFSして子を数えてやるとできる。
#include <cstdio> #include <algorithm> #include <vector> using namespace std; int N; vector<int> T[10001]; vector<int> ans; int dfs(int p, int q){ int sum = 0; bool f = true; for(int i = 0; i < T[q].size(); i++){ if(T[q][i] == p) continue; int t = dfs(q, T[q][i]); f = f && (t <= N / 2); sum += t; } if(f && N - sum - 1 <= N/2) ans.push_back(q); return sum + 1; } int main(){ scanf("%d", &N); for(int i = 0; i < N-1; i++){ int a, b; scanf("%d %d", &a, &b); T[a].push_back(b); T[b].push_back(a); } dfs(-1, 1); sort(ans.begin(), ans.end()); for(int i = 0; i < ans.size(); i++) printf("%d\n", ans[i]); }