妹子在线求助,70分,RE两个点,TLE一个点
查看原帖
妹子在线求助,70分,RE两个点,TLE一个点
31543
paper_plane楼主2020/11/30 19:09
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;
const int N=2000005;
struct Edge{
	long long _to,_next,_dis;
}e[N];
long long tot,head[N],cnt[N],ans[N];
long long n,ans0[N],f[N];
void in(long long &x){
	x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c-'0');
		c=getchar();
	}
}
void add_edge(long long u,long long v,long long w){
	tot++;
	e[tot]._to=v;
	e[tot]._next=head[u];
	e[tot]._dis=w;
	head[u]=tot;
}
void dfs(long long u,long long fa){
	cnt[u]=1;
	f[u]=fa;
	for(long long i=head[u];i;i=e[i]._next){
		long long v=e[i]._to;
		if(v==fa)continue;
		dfs(v,u);
		cnt[u]+=cnt[v];
		ans[u]+=e[i]._dis*cnt[v]+ans[v];
		//ans[v]+=e[i]._dis*(n-cnt[v]);
	}
}
void dfs0(long long u,long long fa){
	for(long long i=head[u];i;i=e[i]._next){
	//	cout<<e[i]._to<<' '<<u<<endl;
		if(e[i]._to==fa)continue;
		for(long long j=head[u];j;j=e[j]._next){
			if(i==j)continue;
			if(e[j]._to==fa){
				ans0[e[i]._to]+=ans0[e[j]._to]+(n-cnt[e[j]._to+1])*e[j]._dis;
				continue;
			}
			ans0[e[i]._to]+=cnt[e[j]._to]*e[j]._dis+ans[e[j]._to];
		}
		ans0[e[i]._to]+=(n-cnt[e[i]._to])*e[i]._dis;
		long long v=e[i]._to;
		if(v==f[u])continue;
		dfs0(v,u);
	}
}
int main(){
	freopen("d.in","r",stdin);
	freopen("d.out","w",stdout);
	in(n);
	for(long long i=1;i<n;i++){
		long long a,b;
		in(a);in(b);		
		add_edge(a,b,1);
		add_edge(b,a,1);
	}
	dfs(1,0);
	dfs0(1,0);
	int id=0;
	for(long long i=1;i<=n;i++){
		if(ans[i]+ans0[i]>maxn)maxn=ans[i]+ans0[i],id=i;
	}	
	printf("%d\n",id);
	/*long long minn=(1ll<<60);
	for(int i=1;i<=n;i++){
		if(ans[i]+ans0[i]<minn)minn=ans[i]+ans0[i],id=i;
	}	
	printf("%d %lld\n",id,minn);*/
	return 0;
}
2020/11/30 19:09
加载中...