Cod sursa(job #856727)

Utilizator stoicatheoFlirk Navok stoicatheo Data 16 ianuarie 2013 21:23:44
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 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;
 
}