Cod sursa(job #978074)

Utilizator manutrutaEmanuel Truta manutruta Data 27 iulie 2013 18:53:26
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 16010

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

long long n;
vector<int> G[MAXN];
long long a[MAXN];
long long solutie;

inline bool cmp(int x, int y) {
    return a[x] > a[y];
}

void DFS(int nd) {

    for (int i = 0; i < G[nd].size(); i++) {
        DFS(G[nd][i]);
        a[nd] += a[G[nd][i]];
    }

    sort(G[nd].begin(), G[nd].end(), cmp);

}

void DFS2(int nd) {

    for (int i = 0; i < G[nd].size(); i++) {
        solutie += 1LL * (i + 1) * a[G[nd][i]];
        DFS2(G[nd][i]);
    }

}

int main()
{

    f >> n;

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

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

    DFS(1);
    solutie += a[1];
    DFS2(1);

    g << solutie;

    return 0;
}