Cod sursa(job #120067)

Utilizator stef2nStefan Istrate stef2n Data 4 ianuarie 2008 10:00:10
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

#define NMAX 16005
struct struct_vertex {long long c; int d;};

int N, A[NMAX];
vector <int> L[NMAX];

bool cmp(struct_vertex a, struct_vertex b)
{
    return a.d>b.d;
}

long long solve(int vertex, int &cnt)
{
    struct_vertex tmp;
    vector <struct_vertex> v;

    cnt=A[vertex];
    for(unsigned int i=0; i<L[vertex].size(); ++i)
    {
        tmp.c=solve(L[vertex][i], tmp.d);
        v.push_back(tmp);
        cnt+=tmp.d;
    }
    sort(v.begin(), v.end(), cmp);

    long long value=A[vertex];
    for(unsigned int i=0; i<v.size(); ++i)
        value+=v[i].c+v[i].d*(i+1);
    return value;
}


int main()
{
    freopen("dosare.in","r",stdin);
    freopen("dosare.out","w",stdout);
    scanf("%d",&N);
    for(int i=2; i<=N; ++i)
    {
        int v;
        scanf("%d",&v);
        L[v].push_back(i);
    }
    for(int i=1; i<=N; ++i)
        scanf("%d",&A[i]);
    int tmp;
    printf("%Ld\n",solve(1, tmp));
    return 0;
}