错误代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6+10;
int n;
vector<int> tree[maxn];
int dep[maxn];
int size[maxn];
int ans[maxn]; //以i为根的答案
bool vis1[maxn], vis2[maxn];
void dfs1(int rt, int depth){
size[rt] = 1;
vis1[rt] = 1;
ans[1] += depth;
dep[rt] = depth;
for(int i = 0; i < tree[rt].size(); i++){
if(!vis1[tree[rt][i]]){
dfs1(tree[rt][i], depth+1);
size[rt] += size[tree[rt][i]];
}
}
}
void dfs2(int rt, int fa){
vis2[rt] = 1;
ans[rt] = ans[fa]-size[rt]+(n-size[rt]);
for(int i = 0; i < tree[rt].size(); i++){
if(!vis2[tree[rt][i]]){
dfs2(tree[rt][i], rt);
}
}
}
signed main(){
scanf("%lld", &n);
for(int i = 1; i < n; i++){
int a, b;
scanf("%lld%lld", &a, &b);
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs1(1, 0); //处理出以1为子树时每个节点的深度
dfs2(1, 1);
int maxx = 0;
for(int i = 1; i <= n; i++) if(ans[i] > ans[maxx]) maxx = i;
printf("%lld", maxx);
return 0;
}
洛谷AC了