10pts求助
  • 板块P1395 会议
  • 楼主XY_world
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/3 14:55
  • 上次更新2023/11/3 17:56:04
查看原帖
10pts求助
545032
XY_world楼主2023/11/3 14:55
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,head[100005],ecnt,ans[100005],dep[100005],depmax,dd,dd1,fa[100005];
struct node{
	int u,v,nxt;
}e[200005];
void addedge(int u,int v){
	ecnt++;
	e[ecnt].u=u;
	e[ecnt].v=v;
	e[ecnt].nxt=head[u];
	head[u]=ecnt;
}
void dfs1(int id,int f){
	dep[id]=dep[f]+1;
	if(dep[id]>depmax){
		depmax=dep[id];
		dd=id;
	}
	for(int i=head[id];i;i=e[i].nxt){
		if(e[i].v==f) continue;
		dfs1(e[i].v,id);
	}
	return;
}
void dfs2(int id,int f){
	dep[id]=dep[f]+1;
	if(dep[id]>depmax){
		depmax=dep[id];
		dd1=id;
	}
	for(int i=head[id];i;i=e[i].nxt){
		if(e[i].v==f) continue;
		fa[e[i].v]=id;
		dfs2(e[i].v,id);
	}
	return;
}
void dfs3(int id,int f){
	ans[id]=ans[f]+1;
	for(int i=head[id];i;i=e[i].nxt){
		if(e[i].v==f) continue;
		dfs3(e[i].v,id);
	}
	return;
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		addedge(u,v);
		addedge(v,u);
	}
	dfs1(1,0);
	depmax=0;
	dfs2(dd,0);
	for(int i=1;i<=depmax/2;i++) dd1=fa[dd1];
	dfs3(dd1,0);
	int nans=0;
	for(int i=1;i<=n;i++) nans+=ans[i];
	cout<<dd1<<" "<<nans-n;
	return 0;
}
2023/11/3 14:55
加载中...