请求加强数据
查看原帖
请求加强数据
1059778
AMLU楼主2024/8/10 10:44

错误代码:

#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了

2024/8/10 10:44
加载中...