水题。。记录每个节点的孩子个数就可以了。。
1 #include <string.h> 2 #include <stdio.h> 3 #include <vector> 4 #include <algorithm> 5 #define MAXN 16001 6 #define INF 0x3f3f3f3f 7 using namespace std; 8 9 struct egde{ 10 int v, n; 11 }e[MAXN*2]; 12 int n, tu, tv, ans; 13 int first[MAXN], es; 14 vector<int> vec; 15 int d[MAXN]; 16 void dp(int u, int f){ 17 d[u] = 1; 18 int tmp = 0; 19 for (int i = first[u]; i != -1; i = e[i].n) { 20 int v = e[i].v; 21 if (v == f) continue; 22 dp(v, u); 23 d[u] += d[v]; 24 tmp = max(tmp, d[v]); 25 } 26 tmp = max(tmp, n - d[u]); 27 if (tmp < ans) vec.clear(), vec.push_back(u), ans = tmp; 28 else if (tmp == ans) vec.push_back(u); 29 } 30 void addedge(int u, int v){ 31 e[es].v = v, e[es].n = first[u], first[u] = es++; 32 } 33 int main(){ 34 scanf("%d", &n); 35 memset(first, -1, sizeof first); es = 0; 36 for (int i = 1; i < n; i++) { 37 scanf("%d%d", &tu, &tv); 38 addedge(tu, tv); 39 addedge(tv, tu); 40 } 41 ans = INF; 42 dp(1, -1); 43 printf("%d %d\n", ans, vec.size()); 44 sort(vec.begin(), vec.end()); 45 for (int i = 0; i < vec.size(); i++){ 46 printf("%d", vec[i]); 47 if (i != vec.size() - 1) printf(" "); 48 } 49 return 0; 50 }