记录编号	205438	评测结果	AAAAAAAAAA
题目名称	不平凡的许愿树	最终得分	100
用户昵称	前鬼后鬼的守护	是否通过	通过
代码语言	C++	运行时间	0.131 s
提交时间	2015-11-05 12:57:47	内存使用	96.29 MiB

#include<cstdio>
#include<cstring>
typedef long long ll;
inline int read(){
	int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x;
}
const int MAXV=5000,D=10,mod=338;
int n,ans,root;
struct edge{
	int y,next;
}e[(MAXV<<1)+D];
int head[MAXV+D],father[MAXV+D];
int num[MAXV+D][MAXV+D],temp[MAXV+D];
void init(){
	n=read();root=1;
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		int k1=i<<1,k2=k1|1;
		e[k1].y=y,e[k1].next=head[x],head[x]=k1;
		e[k2].y=x,e[k2].next=head[y],head[y]=k2;
	}
}
int stack[MAXV+D],top;bool exped[MAXV+D];
int cnt[MAXV+D][5];
void build(){
	stack[++top]=root;
	while(top){
		int x=stack[top];
		if(exped[x]){
			num[x][0]=1;
			for(int i=0;num[x][i];i++)
				num[father[x]][i+1]+=num[x][i];
			top--;
		}
		else{
			for(int i=head[x];i;i=e[i].next)if(e[i].y!=father[x])
				stack[++top]=e[i].y,father[e[i].y]=x;
			exped[x]=1;
		}
	}
	for(int i=0;i<=MAXV;i++)cnt[i][0]=1;
}
bool count(int x,int step){int tot=0;
	if(temp[step])cnt[++tot][1]=temp[step]%mod;
	for(int i=head[x];i;i=e[i].next)if(e[i].y!=father[x]&&num[e[i].y][step-1]){
		tot++;int temp=num[e[i].y][step-1];
		for(int i=1;i<=3;i++)
			cnt[tot][i]=(cnt[tot-1][i]+cnt[tot-1][i-1]*temp)%mod;
	}
	ans=(ans+cnt[tot][3])%mod;
	return tot>=3;
}
void dfs(int x){
	int i;
	for(i=1;;i++)
		if(!count(x,i))
			break;
	for(i=0;;i++)
		if(!temp[i])
			break;
	for(;i;i--)
		temp[i]=temp[i-1];
	for(i=0;num[x][i];i++)
		temp[i]+=num[x][i];
	for(int k=head[x];k;k=e[k].next)if(e[k].y!=father[x]){
		int y=e[k].y;
		for(i=0;num[y][i];i++)
			temp[i+1]-=num[y][i];
		for(i=0;;i++)
			if(!temp[i])
				break;
		for(;i;i--)
			temp[i]=temp[i-1];
		temp[0]=0;
		dfs(y);
		for(i=0;i==0||temp[i];i++)
			temp[i]=temp[i+1];
		for(i=0;num[y][i];i++)
			temp[i+1]+=num[y][i];
	}
	for(i=0;num[x][i];i++)
		temp[i]-=num[x][i];
	for(i=0;temp[i];++i)
		temp[i]=temp[i+1];
}
int main(){
	freopen("hopetree.in","r",stdin);
	freopen("hopetree.out","w",stdout);
	init();
	build();
	dfs(root);
	printf("%d %d",ans+1,(ans+233)%mod+1);
	return 0;
}