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

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <iostream>
#include <algorithm>

template<class Num>void read(Num &x)
{
	char c; int flag = 1;
    while((c = getchar()) < '0' || c > '9')
		if(c == '-') flag *= -1;
	x = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
		x = (x<<3) + (x<<1) + (c-'0');
	x *= flag;
	return;
}
template<class Num>void write(Num x)
{
	if(!x) {putchar('0');return;}
    if(x < 0) putchar('-'), x = -x;
	static char s[20];int sl = 0;
	while(x) s[sl++] = x%10 + '0',x /= 10;
	while(sl) putchar(s[--sl]);
}

const int maxn = 5005, Mod = 338;

int N;
std::pair<int,int> edge[maxn << 1], F[maxn];
int cur[maxn];
#define X first
#define Y second

long long ans = 0;

long long choice(int a,int b)
{
	long long one = 0, two = 0, three = 0;
	
	for(int i = a, j = a; i <= b; i = j)
	{
		while(j <= b && F[j].second == F[i].second) j++;
	
		three += two * (j - i) % Mod;
		two += one * (j - i) % Mod;
		one += j - i;
	}
	
	return three;
}
void dfs(int a,int fa)
{
	F[a] = std::make_pair(F[fa].first + 1, F[fa].second);
	if(F[fa].first == 0) F[a].second = a;
		
	for(int i = cur[a - 1] + 1; i <= cur[a]; i++)
		if(edge[i].Y != fa) dfs(edge[i].Y, a);
}
void init()
{
	int u, v;
	
	read(N);
	for(int i = 1; i < N; i++)
	{
		read(u), read(v);
		edge[i] = std::make_pair(u, v);
		edge[i + (N - 1)] = std::make_pair(v, u);
	}
	std::sort(edge + 1, edge + ((N - 1) << 1) + 1);
	
	for(int i = 1; i <= ((N - 1) << 1); i++) cur[edge[i].X]++;
	for(int i = 1; i <= N; i++) cur[i] += cur[i - 1];
	
}
int main()
{
	freopen("hopetree.in","r",stdin);
	freopen("hopetree.out","w",stdout);
	
	init();
	
	for(int i = 1; i <= N; i++)
	{
		F[i] = std::make_pair(0, i);
		for(int j = cur[i - 1] + 1; j <= cur[i]; j++) dfs(edge[j].Y, i);
		
		std::sort(F + 1, F + N + 1);
		for(int j = 1, k = 1; j <= N; j = k)
		{
			while(k <= N && F[j].first == F[k].first) k++;
			
			ans += choice(j, k - 1), ans %= Mod;
		}
	}
	
	write(ans + 1), putchar(' '), write((ans + 233) % Mod + 1);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}