Cod sursa(job #978067)

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

#define MAXN 16010

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

int n;
vector<int> G[MAXN];
int a[MAXN];
int 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 += (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);

    cout << solutie;

    return 0;
}