C++ 解法, 执行用时: 24ms, 内存消耗: 2580KB, 提交时间: 2020-09-06

#include <vector>
#include <stdio.h>

using namespace std;
 // 使用并查集求出各个子树的最大节点数，即为最后结果
struct DSU {
    vector<int> f, cnt;
    DSU(int n) : f(n), cnt(n, 1) {
        for (int i = 0; i < n; i++)
            f[i] = i;
    }
 
    int find(int x) {
        if (f[x] == f[f[x]]) return f[x];
        return f[x] = find(f[x]);
    }
    bool merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return false;
        f[fy] = fx;
        cnt[fx] += cnt[fy];
        return true;
    }
};
 
int main() {
    int n;
    scanf("%d", &n);
    DSU dsu(n+1);
 
    vector<int> root;
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a == 1) root.push_back(b);
        else if (b == 1) root.push_back(a);
        else dsu.merge(a, b);
    }
    int ans = 0;
    for (int a : root) ans = max(ans, dsu.cnt[dsu.find(a)]);
    printf("%d\n", ans);
    return 0;
 
}

C++ 解法, 执行用时: 25ms, 内存消耗: 1848KB, 提交时间: 2021-08-19

#include <vector>
#include <stdio.h>

using namespace std;
 // 使用并查集求出各个子树的最大节点数，即为最后结果
struct DSU {
    vector<int> f, cnt;
    DSU(int n) : f(n), cnt(n, 1) {
        for (int i = 0; i < n; i++)
            f[i] = i;
    }
 
    int find(int x) {
        if (f[x] == f[f[x]]) return f[x];
        return f[x] = find(f[x]);
    }
    bool merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return false;
        f[fy] = fx;
        cnt[fx] += cnt[fy];
        return true;
    }
};
 
int main() {
    int n;
    scanf("%d", &n);
    DSU dsu(n+1);
    vector<int> root;
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a == 1) root.push_back(b);
        else if (b == 1) root.push_back(a);
        else dsu.merge(a, b);
    }
    int ans = 0;
    for (int a : root) ans = max(ans, dsu.cnt[dsu.find(a)]);
    printf("%d\n", ans);
    return 0;
 
}