样例过全WA求助
  • 板块P1395 会议
  • 楼主luo_xiaoran
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/12/22 11:57
  • 上次更新2023/12/22 17:24:54
查看原帖
样例过全WA求助
605945
luo_xiaoran楼主2023/12/22 11:57
#include<bits/stdc++.h>
#define N 200005
#define int long long
using namespace std;
int pi,ans,n,cnt,head[N],p[N],dp[N];//pi是选择编号,ans是距离和最小值
bool vis[N];//dp[i]是在i点举办会议的距离和,p[i]是i点及其子树的结点总数
struct node{
	int u,v,nxt;
}e[N];
void addd(int u,int v){
	e[++cnt]=node{u,v,head[u]};
	head[u]=cnt;
}
void dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].nxt){
		if(e[i].v==fa) continue;
		dp[e[i].v]=dp[u]+n-2*p[e[i].v];
		dfs(e[i].v,u);
		if(dp[e[i].v]<=ans){
			if(dp[e[i].v]<ans) pi=e[i].v,ans=dp[e[i].v];
			else if(e[i].v<pi) pi=e[i].v;
		}
		ans=min(ans,dp[e[i].v]);
	}
}
void dfs2(int u,int fa){
	for(int i=head[u];i;i=e[i].nxt){
		if(e[i].v==fa) continue;
		dfs2(e[i].v,u);
		p[u]+=p[e[i].v];
		dp[u]+=dp[e[i].v]+p[u];
	}
	p[u]++;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1,x,y;i<n;i++){
		scanf("%lld%lld",&x,&y);
		addd(x,y);
		addd(y,x);
	}
	dfs2(1,0);
	pi=1;
	ans=dp[1];
	dfs(1,0);
	printf("%lld %lld",pi,ans);
	return 0;
}
2023/12/22 11:57
加载中...