Cod sursa(job #2090702)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 18 decembrie 2017 17:20:20
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
ifstream f("dosare.in");
ofstream g("dosare.out");
int N,val[16001],nrac[16001],nrpasi[16001];
long long s;
bool n[16001];
vector <int> G[16001];
void dfs(int nod,int nr){
    n[nod]=1,nrpasi[nod]=nrac[nod];
    for(int i=0;i<G[nod].size();++i)
            if(!n[G[nod][i]]){
                dfs(G[nod][i],nr);
                nrpasi[nod]+=nrpasi[G[nod][i]];
            }
    n[nod]=0;
}
void dfs1(int nod){
    n[nod]=1;
    for(int i=0;i<G[nod].size();++i)
        if(!n[G[nod][i]])
            nrpasi[G[nod][i]]=nrpasi[nod]+i+1,dfs1(G[nod][i]);
}
bool cmp(int X,int Y){
    return nrpasi[X]>nrpasi[Y];
}
int main()
{
    f>>N;
    for(int i=2;i<=N;++i)f>>val[i],G[val[i]].push_back(i);
    for(int i=1;i<=N;++i)f>>nrac[i];
    dfs(1,0);
    for(int i=1;i<=N;++i)
        if(G[i].size())
            sort(G[i].begin(),G[i].end(),cmp);
    memset(nrpasi,0,sizeof(nrpasi));
    nrpasi[1]=1;
    dfs1(1);
    for(int i=1;i<=N;++i)s+=nrac[i]*nrpasi[i];
    g<<s;
    return 0;
}