记录编号	325729	评测结果	AAAAAAAAAA
题目名称	不平凡的许愿树	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.207 s
提交时间	2016-10-20 10:53:11	内存使用	0.38 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstdarg>
#include <string>
#include <list>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 5002
vector<int> G[MAXN];
int deep[MAXN];
int parent[MAXN];
int cnt[MAXN];
int first[MAXN];
/*
void dfs(int u)
{
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];
        if(to != parent[u])
        {
            parent[to] = u;
            deep[to] = deep[u]+1;
            dfs(to);
        }
    }
}
*/
int tmp1[MAXN], tmp2[MAXN];
int dfs(int u, int d)
{
    cnt[d]++;
    int maxd = 1;
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i];
        if(to != parent[u])
        {
            parent[to] = u;
            maxd = max(maxd, dfs(to, d+1)+1);
        }
    }
    return maxd;
}
int main()
{
    freopen("hopetree.in", "r", stdin);
    freopen("hopetree.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for(int i = 1; i < n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    long long ans = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < G[i].size(); j++)
        {
            parent[G[i][j]] = i;
            int maxd = dfs(G[i][j], 1);
            for(int k = 1; k <= maxd; k++)
            {
                ans += tmp2[k]*cnt[k];
                tmp2[k] += tmp1[k]*cnt[k];
                tmp1[k] += cnt[k];
                cnt[k] = 0;
            }
        }
        for(int j = 1; j <= n; j++)
            tmp1[j] = tmp2[j] = 0;
        
        /*
        parent[i] = 0;
        memset(deep, 0, sizeof(deep));
        deep[i] = 1;
        dfs(i);
        sort(deep+1, deep+1+n);
 
        int maxd = 1;
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1; i <= n; i++)
        {
            cnt[deep[i]]++;
            maxd = max(maxd, deep[i]);
        }
        for(int i = 1; i <= maxd; i++)
        {
            ans += cnt[i]*tmp2[i];
            tmp2[i] += tmp1[i]*cnt[i];
            tmp1[i] += cnt[i];
        }
        memset(tmp1, 0, sizeof(tmp1));
        memset(tmp2, 0, sizeof(tmp2));
        */
    }
    printf("%lld %lld", ans%338+1, (ans+233)%338+1);
    return 0;
}