Cod sursa(job #1858085)

Utilizator silkMarin Dragos silk Data 26 ianuarie 2017 23:48:02
Problema Dosare Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define NMax 16000
#define ll long long
using namespace std;

ll dp[NMax+1];
ll nr[NMax+1];
vector<int> a[NMax+1];
int v[NMax+1];
int vf,N;

void DFS(int x)
{
    int i,y,lg = a[x].size();
    int t[lg+1];

    ++vf;
    nr[x] = v[x];
    dp[x] = 1LL * vf * v[x];

    for(i = 0; i < lg; ++i)
    {
        y = a[x][i];
        DFS(y);
        nr[x] += nr[y];
        t[i+1] = nr[y];
        dp[x] += dp[y];
    }
    sort(t+1,t+lg+1);

    for(i = lg; i >= 1; --i) dp[x] += t[i] * (lg-i);
    --vf;
}

int main(){
    FILE* fin = fopen("dosare.in","r");
    FILE* fout = fopen("dosare.out","w");

    int i,x;

    fscanf(fin,"%d",&N);
    for(i = 2; i <= N; ++i)
    {
        fscanf(fin,"%d",&x);
        a[x].push_back(i);
    }
    for(i = 1; i <= N; ++i) fscanf(fin,"%d",&v[i]);

    DFS(1);
    fprintf(fout,"%lld\n",dp[1]);


return 0;
}