记录编号	206219	评测结果	AAAAAAAAAA
题目名称	不平凡的许愿树	最终得分	100
用户昵称	WAHT	是否通过	通过
代码语言	C++	运行时间	3.671 s
提交时间	2015-11-06 10:41:19	内存使用	0.63 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int oo=5500;
int ans=0,m;
int read()
{
	int x=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0',ch=getchar();}
	return x;
}

struct my
{
	int next,y,v;
}e[oo<<1];
int linkk[oo],len;
void insert(int xx,int yy)
{
	e[++len].y=yy;
	e[len].next=linkk[xx];
	linkk[xx]=len;
	e[++len].y=xx;
	e[len].next=linkk[yy];
	linkk[yy]=len;
}

struct one
{
	int deep,node;
}num[oo];
bool cm(one a,one b)
{return (a.deep<b.deep)||(a.deep==b.deep&&a.node<b.node);}

int q[oo],head,tail,deep[oo];
int vis[oo],f=true;
int father[oo],lgt;
int sum[oo],l[oo];
void bfs(int s)
{
	deep[s]=0;
	q[1]=s,tail=1,head=0;
	memset(num,0,sizeof(num));
	memset(vis,0,sizeof(vis));
	lgt=0;
	int enh=0;
	vis[s]=oo;
	while(head++<tail)
	{
		int tn=q[head];
		for(int i=linkk[tn];i;i=e[i].next)
		{	
			int to=e[i].y;
			if(!vis[to])
			{	
				q[++tail]=to;
				vis[to]=vis[tn];
				deep[to]=deep[tn]+1;
				if(deep[tn]==0)
					lgt++,vis[to]=lgt;
				else num[++enh].deep=deep[to],num[enh].node=vis[to];
			}
		}
	}	
	
	if(lgt<3) return;
	int ll=0;
	for(int i=1;i<=lgt-2;i++)
		ll+=i,ans+=ll,ans%=338,ll%=338;
	for(int i=1;i<=lgt;i++)
		l[i]=0;
	sort(num+1,num+enh+1,cm);
	num[0].deep=num[1].deep;
	for(int i=1;i<=enh;i++)
	{	
		if(num[i].deep==num[i-1].deep)	l[num[i].node]++;
		
		if(num[i].deep!=num[i-1].deep||i==enh)
		{
			for(int j=1;j<=lgt;j++)
				sum[j]=sum[j-1]+l[j];
			for(int j=1;j<=lgt;j++)
				for(int h=j+1;h<=lgt;h++)
					ans+=(l[j]*l[h]*(sum[lgt]-sum[h])),ans%=338;
			for(int j=1;j<=lgt;j++)	l[j]=0;
			l[num[i].node]=1;
		}

	}
}
void init()
{
	m=read();
	int a,b;
	for(int i=1;i<m;i++)
	{	a=read(),b=read();	insert(a,b);}
	
	for(int i=1;i<=m;i++)
		bfs(i);
	cout<<ans+1<<' '<<(ans+233)%338+1;
}

int main()
{
	freopen("hopetree.in","r",stdin);
	freopen("hopetree.out","w",stdout);
	
	init();
	return 0;
}