全RE
  • 板块P1395 会议
  • 楼主belif__kibo
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/6 15:51
  • 上次更新2024/8/6 16:35:01
查看原帖
全RE
1261547
belif__kibo楼主2024/8/6 15:51
#include<bits/stdc++.h>
using namespace std;
int n,dis[100010],num[100010],dp[100010],ans,p;
vector<int> e[100010];
void fun(int p)
{
	num[p]=1;
	for(int i=0;i<e[p].size();i++)
	{
		int v=e[p][i];
		if(!dis[v])
		{
			dis[v]=dis[p]+1;
			fun(v);
			num[p]+=num[v];
		}
	}
}
int dfs(int p,int fa)
{
	dp[p]=dp[fa]+n-2*num[p];
	for(int i=0;i<e[p].size();i++)
	{
		int v=e[p][i];
		if(v!=fa) dfs(v,p);
	}
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dis[1]=1;
    fun(1);
    for(int i=1;i<=n;i++) ans+=dis[i];
    ans-=n;
    dp[1]=ans;
    p=1;
    for(int i=0;i<e[1].size();i++) dfs(e[1][i],1);
    for(int i=1;i<=n;i++) if(dp[i]<ans) ans=dp[i],p=i;
    printf("%d %d",p,ans);
}
2024/8/6 15:51
加载中...