记录编号	205702	评测结果	AAAAAAAAAA
题目名称	不平凡的许愿树	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	5.398 s
提交时间	2015-11-05 17:35:13	内存使用	0.45 MiB

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define N 5010
using namespace std;
ifstream in("hopetree.in");
ofstream out("hopetree.out");
int n,m;
vector<int> G[N];
int ans=0,h[N]={0},f[N]={0},g[N]={0},mod=338;
bool l[N]={0};
int dis[N]={0};
int temp=0;
void add(int u,int v)
{
	G[u].push_back(v);
	G[v].push_back(u);
}
void DFS(int u)
{
	int i,v;
	l[u]=1;
	f[dis[u]]++;
	//out<<dis[u]<<' ';
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		if(!l[v])
		{
			dis[v]=dis[u]+1;
			temp=max(temp,dis[v]);
			DFS(v);
		}
	}
}
void BFS(int s)
{
	int i,k,u,v,T;
	for(i=0;i<=n;i++)
	{
		l[i]=0;
		f[i]=g[i]=h[i]=dis[i]=0;
	}
	l[s]=1;
	for(i=0;i<G[s].size();i++)
	{
		v=G[s][i];
		temp=0;
		DFS(v);
		//out<<'*';
		//out<<temp<<' ';
		for(k=0;k<=temp;k++)
		{
			//out<<f[k]<<' ';
		    ans+=f[k]*h[k];
			ans%=mod;
		    h[k]+=g[k]*f[k];
			h[k]%=mod;
		    g[k]+=f[k];
			g[k]%=mod;
			f[k]=0;
		}
		//out<<endl;
	}
	//out<<endl;
	//for(i=1;i<=n;i++)f[dis[i]]++;
	
}
void read()
{
	int i,u,v;
	in>>n;
	m=n-1;
	for(i=1;i<=m;i++)
	{
		in>>u>>v;
		add(u,v);
	}
	for(i=1;i<=n;i++)BFS(i);
	//ans++;
	out<<(ans%338+1)<<' '<<((ans+233)%338+1)<<endl;
}
int main()
{
	read();
	return 0;
}