Cod sursa(job #2088992)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 16 decembrie 2017 10:04:55
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f ("dosare.in");
ofstream g ("dosare.out");
const int nmax=16e3+3;
int n,a,usu[nmax],m[nmax],val[nmax];
vector < pair <int,int> > v[nmax];
long long sol;
void dfs1(int nod,int ant)
{
    usu[nod]=val[nod];
    for(int i=0;i<v[nod].size();++i)
    {
        if(v[nod][i].second!=ant)
        {
            dfs1(v[nod][i].second,nod);
            usu[nod]+=usu[v[nod][i].second];
        }
    }
}
void dfs(int nod,int ant)
{
    for(int i=0;i<v[nod].size();++i)
    {
        if(v[nod][i].second!=ant)
        {
            usu[v[nod][i].second]+=usu[nod]+i+1;
            dfs(v[nod][i].second,nod);
        }
    }
}
int main()
{
    f>>n;
    for(int i=2;i<=n;++i)
    {
        f>>m[i];
    }
    for(int i=1;i<=n;++i) f>>val[i];
    for(int i=2;i<=n;++i)
    {
        v[m[i]].push_back(make_pair(val[i],i));
    }
    dfs1(1,0);
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<v[i].size();++j) v[i][j].first=usu[v[i][j].second];
        sort(v[i].begin(),v[i].end());
        reverse(v[i].begin(),v[i].end());
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<v[i].size();++j) v[i][j].first=val[v[i][j].second];
    }
    for(int i=1;i<=n;++i) usu[i]=0;
    usu[1]=1;
    dfs(1,0);
    for(int i=1;i<=n;++i) sol+=val[i]*usu[i];
    g<<sol;
    return 0;
}