比赛 不平凡的世界 评测结果 AAAAAAAAAA
题目名称 不平凡的许愿树 最终得分 100
用户昵称 膜拜神犇王梦迪 运行时间 4.974 s
代码语言 C++ 内存使用 0.48 MiB
提交时间 2015-11-05 11:48:54
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int L_N=5000+10;
int N;
vector<int> G[L_N];
LL ans;
LL l1[L_N], l2[L_N], tl[L_N];
 
int dfs(int u,int fa,int d){
    tl[d]++;
    int md=1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i]; if(v==fa) continue;
        md=max(md,dfs(v,u,d+1)+1);
    }
    return md;
}
 
int main(){
	freopen("hopetree.in", "r", stdin);
	freopen("hopetree.out", "w", stdout);
    //freopen("in.txt","r",stdin);
    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);
    }
     
    for(int i=1;i<=N;i++){
        for(int j=0;j<G[i].size();j++){
            int v=G[i][j];
            int md=dfs(v,i,1);
            for(int k=1;k<=md;k++){
                ans+=l2[k]*tl[k];
                l2[k]+=l1[k]*tl[k];
                l1[k]+=tl[k];
                tl[k]=0;
            }
        }
        for(int j=1;j<=N;j++){
            l1[j]=l2[j]=0;
        }
        //printf("i:%d ans:%lld\n",i,ans);
    }
 
	int id1 = ans%338+1, id2 = (ans+233)%338+1;
    printf("%d %d\n", id1, id2);
    return 0;
}