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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
#define MAXN 5010
#define PB push_back
#define MP make_pair
typedef pair <int,int> Edge;
typedef long long LL;

	int n,dep_max;
	LL ans=0;
	vector <int> T[MAXN];
	vector <Edge> edges;
	LL dep_cnt[MAXN]={0},dep_sum[MAXN]={0},num[MAXN]={0}; 
	// 1. dep_cnt[i] represents the number of nodes whose depth=i 
	// 2. dep_sum[i] represents the sum of the number of all the nodes which has been visited whose depth =i
	// 3. num[i] represents the number that the pair of nodes which has been visited and are not in the same subtree 

void addedges(int u,int v)
{
	edges.PB(MP(u,v));
	edges.PB(MP(v,u));
	int s=edges.size();
	T[u].PB(s-2);
	T[v].PB(s-1);
}

void dfs(int fa,int x,int dep,int root)
{
	dep_cnt[dep]++;
	dep_max=max(dep_max,dep); // refresh the max depth in the current subtree
	for(int i=0;i<(int)T[x].size();i++)
	{
		Edge& e=edges[T[x][i]];
		if(e.second!=fa)
			dfs(x,e.second,dep+1,root);
		if(x==root)   // one of the subtrees has been completely visited
		{
			for(int i=1;i<=dep_max;i++)
			{
				ans+=dep_cnt[i]*num[i];
				num[i]+=dep_cnt[i]*dep_sum[i];
				dep_sum[i]+=dep_cnt[i];
			}
			dep_max=0;
			memset(dep_cnt,0,sizeof(dep_cnt));
		}
	}
}

void work()
{
	for(int i=1;i<=n;i++)  //  let each node to be the root and do DFS 
	{
		memset(dep_cnt,0,sizeof(dep_cnt));
		memset(dep_sum,0,sizeof(dep_sum));
		memset(num,0,sizeof(num));
		dfs(-1,i,0,i);
	}
}

int main()
{
	freopen("hopetree.in","r",stdin);
	freopen("hopetree.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		addedges(u,v);
	}
	work();
	cout<<ans%338+1<<' '<<(ans+233)%338+1<<endl;
return 0;
}