第一题（NOIP2016）

#include<iostream>
#include<cstring>
using namespace std;
int map[100][100];
int sum[100], weight[100];
int visit[100];
int n;
void dfs(int node) {
    visit[node] = 1;
    sum[node] = 1;
    int maxw = 0;
    for (int v = 1; v <= n; v++) {
        if (!map[node][v] || visit[v])
            continue;
        dfs(v);
        sum[node] += sum[v];
        if (sum[v] > maxw)
            maxw = sum[v];
    }
    if (n - sum[node] > maxw)
        maxw = n - sum[node];
    weight[node] = maxw;
}
int main() {
    memset(map, 0, sizeof(map));
    memset(sum, 0, sizeof(sum));
    memset(weight, 0, sizeof(weight));
    memset(visit, 0, sizeof(visit));
    cin >> n;
    int i, x, y;
    for (i = 1; i < n; i++) {
        cin >> x >> y;
        map[x][y] = 1;
        map[y][x] = 1;
    }
    dfs(1);
    int ans = n, ansN = 0;
    for (i = 1; i <= n; i++) {
        if (weight[i] < ans) {
            ans = weight[i];
            ansN = i;
        }
    }
    cout << ansN << " " << ans << endl;
    return 0;
}

1. 【判断题】ansN 和 ans 的值不可能一样。
   {{ select(1) }}

• 正确
• 错误

2. 【判断题】25~28 行删掉后程序照样输出正常结果。
   {{ select(2) }}

• 正确
• 错误

3. 【判断题】本程序的时间复杂度为 O(n)。
   {{ select(3) }}

• 正确
• 错误

4. 【判断题】38 行的 i++ 改为 ++i 程序照样输出正常结果。
   {{ select(4) }}

• 正确
• 错误

5. 【选择题】输入为：
   11
   1 2
   1 3
   2 4
   2 5
   2 6
   3 7
   7 8
   7 11
   6 9
   9 10
   输出为（ ）。
   {{ select(5) }}

• 2 5
• 3 4
• 4 5
• 3 5

6. 【选择题】n 为 11 时，ans 的值最小为（ ）。
   {{ select(6) }}

• 4
• 5
• 6
• 7