Cod sursa(job #596294)

Utilizator SpiderManSimoiu Robert SpiderMan Data 16 iunie 2011 17:54:17
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
# include <algorithm>
# include <cstdio>
# include <vector>
using namespace std;

typedef long long ll;
const char *FIN = "dosare.in", *FOU = "dosare.out";
const int MAX = 16005;

vector <int> V[MAX];
int N, see[MAX];
ll dp[MAX], cnt[MAX];

inline bool comp (int i, int j) {
    return cnt[i] > cnt[j];
}

void dfs (int N) {
    dp[N] = cnt[N] = see[N];
    for (vector <int> :: iterator i = V[N].begin (); i != V[N].end (); ++i) {
        dfs (*i);
        dp[N] += dp[*i];
        cnt[N] += cnt[*i];
    }
    sort (V[N].begin (), V[N].end (), comp);
    for (size_t i = 0, j = V[N].size (); i < j; ++i)
        dp[N] += cnt[V[N][i]] * (i + 1);
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d", &N);
    for (int i = 2, x; i <= N; ++i) {
        scanf ("%d", &x);
        V[x].push_back (i);
    }
    for (int i = 1; i <= N; ++i)
        scanf ("%d", see + i);
    dfs (1);
    fprintf (fopen (FOU, "w"), "%lld\n", dp[1]);
}