比赛 不平凡的世界 评测结果 AAAAAAAAAA
题目名称 不平凡的许愿树 最终得分 100
用户昵称 Mayuri 运行时间 0.492 s
代码语言 C++ 内存使用 0.47 MiB
提交时间 2017-09-05 19:36:02
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=5011;
const int maxM=maxN*2;
const int Mod=338;
const int inf=2147483647;

int n;
int cnt=0;
int Head[maxN];
int Next[maxM];
int V[maxM];
int ret1[maxN];
int ret2[maxN];
int Depth[maxN];

int read();
void Add_Edge(int u,int v);
int dfs(int u,int father,int depth);

int main()
{
	freopen("hopetree.in","r",stdin);
	freopen("hopetree.out","w",stdout);
	mem(Head,-1);
	n=read();
	for (int i=1;i<n;i++)
	{
		int u=read(),v=read();
		Add_Edge(u,v);
		Add_Edge(v,u);
	}
	int Ans=0;
	for (int i=1;i<=n;i++)//枚举根节点
	{
		//cout<<i<<endl;
		mem(ret1,0);
		mem(ret2,0);
		for (int j=Head[i];j!=-1;j=Next[j])
		{
			//cout<<"  "<<j<<endl;
			mem(Depth,0);
			int depth=dfs(V[j],i,1);
			for (int k=1;k<=depth;k++)
			{
				//cout<<"       "<<k<<endl;
				Ans=(Ans+Depth[k]*ret1[k])%Mod;
				ret1[k]=(ret1[k]+Depth[k]*ret2[k])%Mod;
				ret2[k]=(ret2[k]+Depth[k])%Mod;
			}
		}
	}
	cout<<Ans%Mod+1<<" "<<(Ans+233)%Mod+1<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

int read()
{
	int x=0;
	int k=1;
	char ch=getchar();
	while (((ch>'9')||(ch<'0'))&&(ch!='-'))
		ch=getchar();
	if (ch=='-')
	{
		k=-1;
		ch=getchar();
	}
	while ((ch>='0')&&(ch<='9'))
	{
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*k;
}

void Add_Edge(int u,int v)
{
	cnt++;
	Next[cnt]=Head[u];
	Head[u]=cnt;
	V[cnt]=v;
	return;
}

int dfs(int u,int father,int depth)
{
	Depth[depth]++;
	int max_depth=1;
	for (int i=Head[u];i!=-1;i=Next[i])
	{
		int v=V[i];
		if (v==father)
			continue;
		max_depth=max(max_depth,dfs(v,u,depth+1)+1);
	}
	return max_depth;
}