题解 | #小G有一个大树#

看很多人题解的dfs还要传上一个节点,还有考虑一堆,蒟蒻给像我一样的蒟蒻讲一讲侥幸过的代码

vector<int> r[1001];
int w[1001];
int dp[1001];
void dfs(int x) {
    if (r[x].empty()) {
        w[x]=1;
    } else {
        for (auto y: r[x]) {
//遍历子节点
                dfs(y);

            w[x]+=w[y];
        }
        w[x]++;//记得给自己也算
    }
}
int main() {
    int n;
    while (~scanf("%d",&n)) {
        for (int i = 0; i <= n; ++i) {//初始化
            r[i].clear();
            dp[i]=0;
            w[i]=0;
        }
        for (int i = 1; i < n; ++i) {
            int x, y;
            scanf("%d %d", &x, &y);
            r[x].push_back(y);
//只用把让父节点通向子节点就行
        }
        dfs(1);//遍历给每个点结点数
        int maxn = w[1];
        int minn = INT_MAX;
        memset(dp, -0x3f, sizeof(dp));
//dp[i]代表把i点删除的最大子连通块
        for (int i = 1; i <= n; ++i) {
            if (!r[i].empty()) {//先遍历子节点,因为有可能某子节点的块最大
                for (auto y:r[i]) {
                    dp[i] = max(dp[i], w[y]);
                }
            }
            if (maxn != w[i]) {//防止删1号节点
                dp[i] = max(maxn - w[i], dp[i]);//maxn代表整棵树的结点数
            }
            minn = min(minn, dp[i]);//最小连通块
        }
        for (int i = 1; i <= n; ++i) {
            if (dp[i] == minn) {
                printf("%d %d\n", i, minn);
                return 0;
            }
        }
    }
}