Cod sursa(job #120056)

Utilizator cupacatenumaratecupacatenumarate cupacatenumarate Data 4 ianuarie 2008 01:30:45
Problema Dosare Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define NMAX (1<<14)

using namespace std;

vector<int> A[NMAX];
vector<pair<int,int> > P;
int N, Ac[NMAX], F[NMAX], t[NMAX];
long long No[NMAX];

void read()
{
        int i, j;

        freopen("dosare.in", "r", stdin);
        scanf("%d", &N);

        Ac[0] = 1;
        for (i = 2; i <= N; i++)
        {
                scanf("%d", &j);
                A[i].push_back(j);
                A[j].push_back(i);
        }

        A[1].push_back(0);
        for (i = 1; i <= N; i++) scanf("%d", Ac+i);
}

void solve(int i)
{
        int j, n = A[i].size(), f, fiu;

        F[i] = 1;

        if (n==1&&i>0)
        {
                No[i] = Ac[i];
                return;
        }
        
        for (j = 0; j < n; j++)
            if (!F[ A[i][j] ])
            {
                t[ A[i][j] ] = i;
                solve(A[i][j]);
            }

        No[i] = 0; P.clear();
        for (j = 0; j < n; j++) P.push_back(make_pair(No[A[i][j]], A[i][j]));

        sort(P.begin(), P.end());

        for (j = 0, f = n-1; j < n; j++)
        {
            fiu = P[j].second;
            if (t[i] != fiu)
               No[i] = No[i]+(No[fiu]+f+1), f--;
        }
        No[i] = No[i]*Ac[i];
}

void write()
{
        freopen("dosare.out", "w", stdout);
        printf("%lld\n", No[1]+Ac[1]*(A[1].size()-1)-1);
}

int main()
{
        read();
        solve(1);
        write();
        return 0;
}