记录编号	446326	评测结果	AAAAAAAAAA
题目名称	不平凡的许愿树	最终得分	100
用户昵称	Ostmbh	是否通过	通过
代码语言	C++	运行时间	1.158 s
提交时间	2017-09-07 21:44:59	内存使用	191.95 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=5010;
int f[5010][5010];
int g[5010][5010];
vector<int>A[5010];
int cou[5010];
int now=0;
long long ans=0;
int n;
int dfn[maxn],size[maxn];
int ti=0;
int vis[maxn];
inline void dfs1(int x,int d){
	dfn[x]=++ti;
	size[x]=1;
	for(int i=0;i<A[x].size();i++){
		int u=A[x][i];
		if(u==d)
			continue;
		dfs1(u,x);
		size[x]+=size[u];
	}
}
inline void dfs(int x,int d){
	if(dfn[x]<dfn[now]||dfn[x]>=dfn[now]+size[now])
		g[now][d]++;
	vis[x]=1;
	for(int i=0;i<A[x].size();i++){
		int u=A[x][i];
		if(vis[u])
			continue;
		dfs(u,d+1);
	}
}
inline void work(int x,int d){
	int cou[maxn];
	for(int i=1;i<=n;i++)
		cou[i]=0;
	for(int i=0;i<A[x].size();i++){
		int u=A[x][i];
		if(u==d)
			continue;
		work(u,x);
		for(int j=1;j<=n;j++){
			ans+=cou[j]*f[u][j-1];
			cou[j]+=f[u][j-1]*f[x][j];
			f[x][j]+=f[u][j-1];
		}
	}
	for(int i=1;i<=n;i++)
		ans+=cou[i]*g[x][i];
}
int main(){
	freopen("hopetree.in","r",stdin);
	freopen("hopetree.out","w",stdout);
	scanf("%d",&n);
	int x,y;
	for(int i=1;i<n;i++){
		scanf("%d %d",&x,&y);
		A[x].push_back(y);
		A[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
		f[i][0]=1;
	dfs1(1,0);
	for(int i=n;i>=1;i--){
		memset(vis,0,sizeof(vis));
		now=i;
		dfs(i,0);
	}
	work(1,0);
	cout<<ans%338+1<<' '<<(ans+233)%338+1<<endl;
return 0;
}