Cod sursa(job #718547)

Utilizator vendettaSalajan Razvan vendetta Data 20 martie 2012 21:23:45
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define nmax 16005
#define ll long long

using namespace std;

ifstream f("dosare.in");
ofstream g("dosare.out");

int n, d[nmax], v[nmax];
vector<int> gf[nmax];
ll accesari[nmax];//accesari[i] = nr, numarul de accesari pentru nodul i
ll s;

void citeste(){

    f >> n;
    for(int i=2; i<=n; i++){
        int x;
        f >> x;
        gf[x].push_back(i);
    }

    for(int i=1; i<=n; i++) f >> v[i];

    for(int i=1; i<=n; i++) d[i] = v[i];
    accesari[1] = 1;

}


bool cmp(int a, int b){

    return d[a] > d[b];

}

void dfs_1(int nod){

    for(int i=0; i<gf[nod].size(); i++){
        int vc = gf[nod][i];
        dfs_1(vc);
        d[nod] += d[vc];
    }

    sort(gf[nod].begin(), gf[nod].end(), cmp);

}

void calcul(int nod){

    s += accesari[nod]*v[nod];

    for(int i=0; i<gf[nod].size(); i++){
        int vc = gf[nod][i];
        accesari[vc] = (accesari[nod] + i*1LL + 1LL);
        calcul(vc);
    }

}

void scrie(){

    g << s << "\n";

}

int main(){

    citeste();
    dfs_1(1);
    calcul(1);
    scrie();

    f.close();
    g.close();

    return 0;

}