# 11392: 【原1392】BJ_drunbier

### 题目描述

author: 徐世超 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1392

## Input Format

``````第一行，一个正整数N。

``````

## Output Format

``````一行一个数，是平均路径长度，保留两位小数。
``````

## Sample Input

``````4
2 1
0 0
2 1
2 1
``````

## Sample Output

``````1.50
``````

## 数据范围与约定

``````N≤10000。一个节点的父节点不会是自己。
``````

## FineArtz's solution

``````/* BJ_drunbier */
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

class Node{
public:
vector<int> edge;
int sub = 1;
};
class Edge{
public:
int u = 0, v = 0, len = 0;
};

Node a[10005];
Edge e[10005];

int calcSub(int root){
for (auto i : a[root].edge){
a[root].sub += calcSub(i);
}
return a[root].sub;
}

int main(){
int n, f, w, root, cnte = 0;
cin >> n;
if (n == 1){
cout << "0.00" << endl;
return 0;
}
for (int i = 1; i <= n; ++i){
cin >> f >> w;
if (f == 0){
root = i;
}
else{
a[f].edge.push_back(i);
++cnte;
e[cnte].u = f;
e[cnte].v = i;
e[cnte].len = w;
}
}
calcSub(root);
//for (int i = 1; i <= n; ++i)
//    cout << i << ' ' << a[i].sub << endl;
double ans = 0, tmp;
for (int i = 1; i <= cnte; ++i){
tmp = n - a[e[i].v].sub;
tmp = tmp * a[e[i].v].sub;
tmp = tmp * e[i].len;
ans = ans + tmp;
}
ans = ans / n / (n - 1) * 2;
cout << setiosflags(ios::fixed) << setprecision(2) << ans << endl;
return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
using namespace std;
double sum;
long long l[10001];
int num,n,nxt[10001],last[10001],to[10001],root,f,v;
num++;
nxt[num]=last[x];
last[x]=num;
to[num]=y;
l[num]=v;
}
int dfs(int x){
int son=1,tmp;
for (int i=last[x];i!=0;i=nxt[i]){
tmp=dfs(to[i]);
son+=tmp;
sum+=(n-tmp)*tmp*l[i];
}
return son;
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;++i){
scanf("%d%d",&f,&v);
if (f==0) root=i;