WA+RE求调
查看原帖
WA+RE求调
1409685
zhaoyikuan_kkk楼主2025/7/22 21:58

水了好几道直径的蓝题然后发现板子题过来提交居然挂了

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 10100;
int n, siz[maxn], f[maxn];
vector<int> G[maxn];
// 求以 u 为根结点的子树大小
// 以及 u 的最大子树的结点数量
// f[u] = max{siz[v], n-siz[u]}
int dfs(int u, int fa) { 
    siz[u] = 1; 
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v != fa) {
            siz[u] += dfs(v, u);
            // 更新 f[u] = max{siz[v]}
            f[u] = max(f[u], siz[v]);
        }
    }
    // 更新 f[u] = max{f[u], n-siz[u]}
    f[u] = max(f[u], n - siz[u]);
    return siz[u];
}
int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 1);
    int center = 1;
    for (int i = 1; i <= n; i++) {
        // 找到 f[i] 最小的结点 center
        if (f[i] < f[center]) {
            center = i;
        }
    }
    cout << center << endl;
    return 0;
}

2025/7/22 21:58
加载中...