/ Randle /

记录详情

Runtime Error


  
# 状态 耗时 内存占用
#1 Wrong Answer 49ms 66.426 MiB
#2 Wrong Answer 31ms 70.43 MiB
#3 Wrong Answer 52ms 66.566 MiB
#4 Runtime Error 175ms 106.305 MiB
#5 Runtime Error 174ms 105.676 MiB
#6 Runtime Error 237ms 120.43 MiB
#7 Runtime Error 302ms 115.926 MiB
#8 Runtime Error 323ms 119.391 MiB
#9 Runtime Error 258ms 117.07 MiB
#10 Runtime Error 210ms 110.93 MiB

代码

#include<bits/stdc++.h>
const long long maxn=2e6+1;
inline const void read(long long &a)
{
	char c=getchar();a=0;
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		a=(a<<1)+(a<<3)+c-'0';
		c=getchar();
	}
}
long long n,d=0,kk=1;
long long point[maxn],next[maxn],father[maxn],to[maxn],ans[maxn],num[maxn],sum[maxn],deep[maxn];
bool vis[maxn];
inline const void add(long long a,long long b)
{
	next[++d]=point[a];
	point[a]=d;
	to[d]=b;
}
inline const void dfs1(long long p)
{
	vis[p]=true;
	long long side=point[p];
	num[p]=1;sum[p]+=deep[p];
	while(side)
	{
		if(!vis[to[side]])
		{
			father[to[side]]=p;
			deep[to[side]]=deep[p]+1;
			dfs1(to[side]);
			num[p]+=num[to[side]];sum[p]+=sum[to[side]];
		}
		side=next[side];
	}
}
inline const void dfs2(long long p)
{
	
	if(p!=1)ans[p]=ans[father[p]]-2*num[p]+num[1];
	if(ans[p]>ans[kk])kk=p;
	if(ans[p]==ans[kk]&&p<kk)kk=p;
	vis[p]=true;
	long long side=point[p];
	while(side)
	{
		if(!vis[to[side]])dfs2(to[side]);
		side=next[side];
	}
}
int main()
{
	memset(father,0,sizeof(father));
	memset(sum,0,sizeof(sum));
	memset(point,0,sizeof(point));
	memset(ans,0,sizeof(ans));
	read(n);
	long long u,v;
	for(long long i=1;i<=n-1;i++){read(u);read(v);add(u,v);add(v,u);}
	deep[1]=0;
	memset(vis,false,sizeof(vis));
	dfs1(1);
	memset(vis,false,sizeof(vis));ans[1]=sum[1];
	std::cout<<std::endl;
	dfs2(1);
	std::cout<<kk;
	return  0;
}

信息

递交者
类型
递交
题目
树的深度 T1
题目数据
下载
语言
C++
递交时间
2017-10-11 19:45:06
评测时间
2017-10-11 19:45:06
评测机
分数
0
总耗时
1815ms
峰值内存
120.43 MiB