50pts求调orz
  • 板块P1395 会议
  • 楼主JOEYyyyyfuck
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/5 18:26
  • 上次更新2024/4/5 20:21:42
查看原帖
50pts求调orz
683031
JOEYyyyyfuck楼主2024/4/5 18:26
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> tree[50004];
int subsize[50004];
int result[50004];
int depth[50004];
int deep = 0;
int result_final;
int result_index;
int dfs(int x,int fa)
{
	int all = 0;
	deep++;
	for (int i = 0; i < tree[x].size(); i++)
	{
		if (tree[x][i] == fa) continue;
		depth[tree[x][i]] = deep;
		all += dfs(tree[x][i], x);
	}
	all++;
	subsize[x] = all;
	deep--;
	return all;
}
void dfs2(int x,int fa)
{
	for (int i = 0; i < tree[x].size(); i++)
	{
		if (tree[x][i] == fa) continue;
		result[tree[x][i]] = result[x] + n - 2 * subsize[tree[x][i]];
		if (result_final > result[tree[x][i]])
		{
			result_final = result[tree[x][i]];
			result_index = tree[x][i];
		}
		dfs2(tree[x][i], x);
	}
}
int main()
{
	scanf("%d",&n);
	int x, y;
	for (int i = 1; i <= n - 1; i++)
	{
		scanf("%d %d", &x, &y);
		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	dfs(1, 0);
	for (int i = 2; i <= n; i++) result[1] += depth[i];
	result_final = result[1];
	result_index = 1;
	dfs2(1, 0);
	printf("%d %d", result_index, result_final);
}
2024/4/5 18:26
加载中...