Cod sursa(job #1768900)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 1 octombrie 2016 17:30:57
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
# include <fstream>
# include <vector>
# include <algorithm>
# define DIM 16010
# define f first
# define s second
using namespace std;
ifstream fin("dosare.in");
ofstream fout("dosare.out");
vector <int> Lista[DIM];
pair <int,int> v[DIM];
int Marcat[DIM],t[DIM],n,i,x,k;
long long nr[DIM],p[DIM],s;
void dfs1(int nc){
    Marcat[nc]=1;
    for(int i=0;i<Lista[nc].size();i++){
        int nv=Lista[nc][i];
        if(!Marcat[nv])
            dfs1(nv);
    }
    nr[t[nc]]+=nr[nc];
}
void dfs2(int nc){
    Marcat[nc]=1;
    for(int i=0;i<Lista[nc].size();i++){
        int nv=Lista[nc][i];
        if(!Marcat[nv]){
            s+=1LL*nr[nv]*(i+1);
            dfs2(nv);
        }
    }
}
int main () {
    fin>>n;
    for(i=2;i<=n;i++){
        fin>>x;
        Lista[x].push_back(i);
        t[i]=x;
    }
    for(i=1;i<=n;i++)
        fin>>nr[i];
    dfs1(1);
    for(i=1;i<=n;i++){
        k=0;
        for(x=0;x<Lista[i].size();x++){
            v[++k].s=Lista[i][x];
            v[k].f=nr[Lista[i][x]];
        }
        sort(v+1,v+k+1);
        for(x=0;x<Lista[i].size();x++)
            Lista[i][x]=v[Lista[i].size()-x].s;
    }
    for(i=1;i<=n;i++)
        Marcat[i]=0;
    s=1LL*nr[1];
    dfs2(1);
    fout<<s<<"\n";
    return 0;
}