不知道为什么,WA了5个点
  • 板块P1395 会议
  • 楼主gylgygdhg
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/2/12 12:02
  • 上次更新2023/10/24 01:00:35
查看原帖
不知道为什么,WA了5个点
730956
gylgygdhg楼主2023/2/12 12:02
#include <bits/stdc++.h>
using namespace std;
long long n,a,b,tot,h[6000005],f[6000005],mf=0x3f3f3f3f,size[6000005],id;
struct node{
	long long v,next;
}e[6000005];
void addedge(int u,int v){
	e[++tot].v=v;
	e[tot].next=h[u];
	h[u]=tot;
}
void dfs(int u,int fa){
	size[u]=1;
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].v;
		if(v==fa){
			continue;
		}
		dfs(v,u);
		size[u]+=size[v];
	}
	
}
void dfs1(long long u,long long fa){
	for(long long i=h[u];i;i=e[i].next){
		long long v=e[i].v;
		if(v==fa){
			continue;
		}
		f[v]=f[u]+n-2*size[v];
		if(f[v]<mf){
			mf=min(mf,f[v]);
			id=v;
		}
		dfs1(v,u);
	}
}
int main(){
	scanf("%d",&n);
	for(long long i=1;i<=n-1;i++){
		scanf("%d%d",&a,&b);
		addedge(a,b);
		addedge(b,a);
	}
	dfs(1,0);
	for(long long i=2;i<=n;i++) f[1]+=size[i];
	dfs1(1,0);
	cout<<id<<" "<<mf;
	return 0;
}
2023/2/12 12:02
加载中...