为什么CE了,每次都是这样,CF=CE,UVA交不上去,是我太菜了吗?
查看原帖
为什么CE了,每次都是这样,CF=CE,UVA交不上去,是我太菜了吗?
213196
Wens楼主2020/11/29 10:59
#include<stdio.h>
#include<iostream>
#define ll long long
#define N 1000010
using namespace std;

ll read(){
	ll w=0,x=0;char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return w?-x:x;
}

ll n,ans;
ll next[N<<1],to[N<<1],head[N],cnt=1;
ll f[N],siz[N],v[N],dep[N];

void add(ll x,ll y){
	next[++cnt]=head[x];
	to[cnt]=y;
	head[x]=cnt;
	return ;
}

void dfs1(ll p,ll fa){
	siz[p]=1;
	v[p]=dep[p]=dep[fa]+1;
	for(ll i=head[p];i;i=next[i]){
		ll tt=to[i];
		if(tt==fa)continue;
		dfs1(tt,p);
		siz[p]+=siz[tt];
		v[p]+=v[tt];
	}
	return ;
}
void dfs2(ll p,ll fa){
	if(fa)f[p]=f[fa]+n-siz[p]*2;
	else f[p]=v[p];
	for(ll i=head[p];i;i=next[i]){
		ll tt=to[i];
		if(tt==fa)continue;
		dfs2(tt,p);
	}
}
int main(){
	n=read();
	for(int i=1;i<=n-1;++i){
		ll x=read(),y=read();
		add(x,y);
		add(y,x);
	}
	dfs1(1,0);
	dfs2(1,0);
/*	cout<<"---------------------"<<endl;
	for(ll i=1;i<=n;++i){
		cout<<i<<" "<<siz[i]<<" "<<v[i]<<endl;
	}
	cout<<"---------------------"<<endl;
	for(ll i=1;i<=n;++i){
		cout<<i<<" "<<f[i]<<endl;
	}
*/	
	for(int i=1;i<=n;++i){
		if(f[i]>f[ans])ans=i;
	}
	cout<<f[ans]<<endl;
	return 0;
}
2020/11/29 10:59
加载中...