平均树高★实验任务我们知道,在图论中,有根树中的节点可以根据到根的距离分层(假设根为第一层).一棵有根数的层数叫做这棵树的高度.现在我们定义一棵树的平均高度为该树的所有子树(包

Question

平均树高
★实验任务
我们知道,在图论中,有根树中的节点可以根据到根的距离分层(假设根为第一层).一
棵有根数的层数叫做这棵树的高度.现在我们定义一棵树的平均高度为该树的所有子树(包
括自身)的高度的平均数.那么现在给出一颗树,你能求出该树的平均高度吗?
★数据输入
输入第一行一个正整数
N (2 < N < 10000) 表示该树有
N个结点.
接下来
N-1行,每行两个整数
ab,表示
a是
b的父亲结点,数据保证所给的是一棵树,
结点的编号为
1到
N.
★数据输出
输出一行一个整数,表示该树的平均高度,结果保留
3位小数.
输入示例 输出示例
7 1.857
1 2
1 3
1 4
3 5
3 6
6 7

Answer 1

#define N 10010
#define CL(X) memset(X,0,sizeof(X))
#define for if(0);else for
#include
#include
#include
#include
using namespace std;
int h[N];
int in[N];
vector a[N];
int root;
int n;
int max(int a,int b)
{
return a>b?a:b;
}
int dfs(int x)
{
if(h[x]!=0) return h[x];
else
{
int _max=1;
for(int i=0;i {
_max=max(_max,dfs(a[x][i])+1);
}
h[x]=_max;
return h[x];
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
CL(h);
CL(in);
for(int i=0;i<=n;i++) a[i].clear();
for(int i=0;i {
int ta,tb;
scanf("%d %d",&ta,&tb);
a[ta].push_back(tb);
in[tb]++;
}
for(int i=1;i<=n;i++) if(in[i]==0) {root=i;break;}
dfs(root);
double ans=0;
for(int i=1;i<=n;i++) ans+=h[i];
ans/=n;
printf("%.3lf\n",ans);
}
return 0;
}