记录编号	205472	评测结果	AAAAAAAAAA
题目名称	不平凡的许愿树	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	3.142 s
提交时间	2015-11-05 14:08:22	内存使用	172.39 MiB

/*
Problem:cogs2096;
Language:c++;
by dydxh;
2015.11.05;
*/
#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<utility>
#include<ctime>
#include<cstdlib>
#include<bitset>
#include<string>
#define ll long long
#define ull unsigned long long
using namespace std;
const int oo=2000000000;
const int maxn=5005;
const int mod=338;
int n,len,Limit,ans;
int linkk[maxn],Dep[maxn];
int Down[maxn][maxn],Uper[maxn][maxn];
struct edge{
	int y,next;
}e[maxn<<1];
inline int read(){
	int x=0;bool flag=0;char ch=getchar();
	while(ch>'9' || ch<'0') {if(ch=='-') flag=1;ch=getchar();}
	while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return flag?-x:x;
}
void insert(int a,int b){
	e[++len].next=linkk[a];
	linkk[a]=len,e[len].y=b;
	e[++len].next=linkk[b];
	linkk[b]=len,e[len].y=a;
}
void Dfs_Down(int x,int Fa){
	Down[x][0]=1;
	for(int i=linkk[x];i;i=e[i].next){
		int tn=e[i].y;
		if(tn==Fa) continue;
		Dfs_Down(tn,x);
		for(int j=1;j<=Limit;j++)
			Down[x][j]=(Down[x][j]+Down[tn][j-1])%mod;
	}
}
void Dfs_Uper(int x,int Fa){
	Uper[x][0]=1;
	if(x!=1){
		Uper[x][1]=1;
		for(int i=2;i<=Limit;i++)
			Uper[x][i]=(Uper[Fa][i-1]+Down[Fa][i-1]-Down[x][i-2])%mod;
	}
	for(int i=linkk[x];i;i=e[i].next){
		int tn=e[i].y;
		if(tn==Fa) continue;
		Dfs_Uper(tn,x);
	}
}
void Dfs_Ans(int x,int Fa){
	int Coup[maxn],Sum[maxn];
	for(int i=0;i<=Limit;i++)
		Coup[i]=0,Sum[i]=0;
	for(int i=linkk[x];i;i=e[i].next){
		int tn=e[i].y;
		if(tn==Fa) continue;
		Dfs_Ans(tn,x);
		for(int j=1;j<=Limit;j++){
			ans=(ans+Down[tn][j-1]*Coup[j])%mod;
			Coup[j]=(Coup[j]+Sum[j]*Down[tn][j-1])%mod;
			Sum[j]=(Sum[j]+Down[tn][j-1])%mod;
		}
	}
	for(int j=1;j<=Limit;j++)
		ans=(ans+Uper[x][j]*Coup[j])%mod;
}
int main()
{
	//freopen("cc.in","r",stdin);
	freopen("hopetree.in","r",stdin);
	freopen("hopetree.out","w",stdout);
	n=read(),Limit=n-1;
	for(int i=1;i<n;i++) insert(read(),read());
	Dfs_Down(1,0);
	Dfs_Uper(1,0);
	Dfs_Ans(1,0);
	//cout<<ans<<endl;
	int A=ans%mod+1,B=(ans+233)%mod+1;
	printf("%d %d\n",A,B);
	return 0;
}