MLE求调
  • 板块P1395 会议
  • 楼主WangYaoran
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/7 16:07
  • 上次更新2024/8/7 16:50:31
查看原帖
MLE求调
1278291
WangYaoran楼主2024/8/7 16:07
#include<bits/stdc++.h>
using namespace std;
const int N = 50005;
int n, ft[N], nx[N], to[N], dp[N], ct[N], fa[N];
int idx, ans, minn = 0x3f3f3f3f;
void add(int x, int y){
	idx++;
	nx[idx] = ft[x];
	ft[x] = idx;
	to[idx] = y;
}
void dfs(int u, int st){
	for (int i = ft[u]; i; i = nx[i]){
		if (to[i] == fa[u]) continue;
		ct[u]++;
		fa[to[i]] = u;
		dfs(to[i], st + 1);
		ct[u] += ct[to[i]];
	}
	dp[1] += st;
}
void find(int x){
	for (int i = ft[x]; i; i = nx[i]){
		if (to[i] == fa[x]) continue;
		dp[to[i]] = dp[x] - ct[to[i]] - 1 + (n - ct[to[i]] - 1);
		find(to[i]);
	}
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++){
		int a, b;
		cin >> a >> b;
		add(a, b); add(b, a);	
	}
	dfs(1, 0);
	find(1);
	for (int i = 1; i <= n; i++){
		if (dp[i] < minn){
			minn = dp[i];
			ans = i;
		}
	}
	cout << ans << " " << minn;
	return 0;
}
2024/8/7 16:07
加载中...