比赛 |
不平凡的世界 |
评测结果 |
AAAAAAAAAA |
题目名称 |
不平凡的许愿树 |
最终得分 |
100 |
用户昵称 |
Mayuri |
运行时间 |
0.492 s |
代码语言 |
C++ |
内存使用 |
0.47 MiB |
提交时间 |
2017-09-05 19:36:02 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
const int maxN=5011;
const int maxM=maxN*2;
const int Mod=338;
const int inf=2147483647;
int n;
int cnt=0;
int Head[maxN];
int Next[maxM];
int V[maxM];
int ret1[maxN];
int ret2[maxN];
int Depth[maxN];
int read();
void Add_Edge(int u,int v);
int dfs(int u,int father,int depth);
int main()
{
freopen("hopetree.in","r",stdin);
freopen("hopetree.out","w",stdout);
mem(Head,-1);
n=read();
for (int i=1;i<n;i++)
{
int u=read(),v=read();
Add_Edge(u,v);
Add_Edge(v,u);
}
int Ans=0;
for (int i=1;i<=n;i++)//枚举根节点
{
//cout<<i<<endl;
mem(ret1,0);
mem(ret2,0);
for (int j=Head[i];j!=-1;j=Next[j])
{
//cout<<" "<<j<<endl;
mem(Depth,0);
int depth=dfs(V[j],i,1);
for (int k=1;k<=depth;k++)
{
//cout<<" "<<k<<endl;
Ans=(Ans+Depth[k]*ret1[k])%Mod;
ret1[k]=(ret1[k]+Depth[k]*ret2[k])%Mod;
ret2[k]=(ret2[k]+Depth[k])%Mod;
}
}
}
cout<<Ans%Mod+1<<" "<<(Ans+233)%Mod+1<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}
int read()
{
int x=0;
int k=1;
char ch=getchar();
while (((ch>'9')||(ch<'0'))&&(ch!='-'))
ch=getchar();
if (ch=='-')
{
k=-1;
ch=getchar();
}
while ((ch>='0')&&(ch<='9'))
{
x=x*10+ch-48;
ch=getchar();
}
return x*k;
}
void Add_Edge(int u,int v)
{
cnt++;
Next[cnt]=Head[u];
Head[u]=cnt;
V[cnt]=v;
return;
}
int dfs(int u,int father,int depth)
{
Depth[depth]++;
int max_depth=1;
for (int i=Head[u];i!=-1;i=Next[i])
{
int v=V[i];
if (v==father)
continue;
max_depth=max(max_depth,dfs(v,u,depth+1)+1);
}
return max_depth;
}