#1本地测试正确,提交后4RE 6TLE??
查看原帖
#1本地测试正确,提交后4RE 6TLE??
22716
神仙酱楼主2024/3/15 01:26
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+10;
int e[N<<1],h[N<<1],nxt[N<<1], idx;
int f[N], sz[N], dep[N], n;
int add(int a, int b){
    e[idx] = b, nxt[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    for(int i=h[u]; i != -1; i=nxt[i]){
        int son = e[i];
        if(son == fa)
            continue;
        dfs(son, u);
        sz[u]+=sz[son];
    }
    sz[u]+=1;
}

void dfs2(int u, int fa) {
    for(int i=h[u]; i != -1; i=nxt[i]){
        int son = e[i];
        if(son == fa)
            continue;
        f[son]=f[u]+(n-sz[son])-sz[son];
        dfs2(son, u);
    }
}
signed main() {
    memset(h, -1, sizeof h);
    cin>>n;
    for(int i=1;i<n;++i) {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    dfs(1,0);
    f[1] = accumulate(dep+1,dep+1+n,0);
    dfs2(1,0);
    cout<<(max_element(f+1,f+1+n)-f);
}
2024/3/15 01:26
加载中...