Skip to content

11392: 【原1392】BJ_drunbier

题目

题目描述

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

Description

哔酱找到了一份酱星人居住地的地图,上面标注着A酱,B酱,C酱,辣酱,甜面酱,蛋黄酱,果酱,上酱,螺旋酱,沙茶酱,等等等等等等酱(好像混进去了很多奇怪的东西)的居住地,它们都散布在乡村田园中。

这N个居住地由乡间小路连成了一棵树。

哔酱在田园间彳(chi)亍(chu)着, 这样迟迟的日影, 这样温暖的寂静, 这片午饮的香味, 对他是多么熟稔。

这带露台,这扇窗, 后面有幸福在窥望, 还有几架书,两张床, 一瓶花......这已是天堂。

这条路他曾经走了多少回! 多少回?......过去都压缩成一堆, 叫人不能分辨,日子是那么相类, 同样幸福的日子,这些孪生姊妹!

是不是今天出门时忘记说“再见”? 是不是早已忘记了田间那芬芳的油菜花香 忘记了交横的乡间小路 于是,他开始沉思: 对所有这乡间小路上的点对(a,b)组成的路径,平均的路径长度是多少?

Input Format

第一行,一个正整数N。

接下来N行,第i行一个数mi,代表节点i的父节点是mi;第二个数li,代表mi到i的边权为li。

特别的,如果i=0代表无父节点。

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;
void add(int x,int y,int 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;
        else add(f,i,v);
    }
    dfs(root);
    printf("%.2f",sum/(n*(n-1)/2));
    return 0;
}