求助(玄关)
  • 板块题目总版
  • 楼主Danny_chan
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/30 22:20
  • 上次更新2024/12/1 09:17:59
查看原帖
求助(玄关)
1032960
Danny_chan楼主2024/11/30 22:20

这里

代码:

#include<bits/stdc++.h> 
#define int long long
using namespace std;
int f[100010],s[100010],d[100010];
int n,t,sum=0;
vector<int>a[100010];
void dfs(int u,int fa){
	s[u]=1;
	f[u]=0;
	for(int i=0;i<a[u].size();i++){
		int v=a[u][i];
		if(v==fa) continue;
		dfs(v,u);
		s[u]+=s[v];
		f[u]=max(f[u],s[v]);
		f[u]=max(f[u],n-s[u]);
		if(f[u]<f[t]||(f[u]==f[t]&&u<t)){
			t=u;
		} 
	}
}
void bfs(){
	queue<int>q;
	q.push(t);
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		for(int i=0;i<a[u].size();i++){
			int v=a[u][i];
			if(d[v]>0&&v==t) continue;
			d[v]=d[u]+1;
			sum+=d[v];
			q.push(v);
		}
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	} 
	t=0;
	f[0]=1e18;
	dfs(1,0);
	bfs();
	cout<<t<<" "<<sum<<endl;
	return 0;
}
2024/11/30 22:20
加载中...