Cod sursa(job #1744411)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 19 august 2016 18:55:23
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 16000
vector <int> G[MAXN+1];
long long dp[MAXN+1];
long long nr[MAXN+1];
int v[MAXN+1];
bool cmp(int a,int b){
   return nr[a]>nr[b];
}
void DFS(int nod){
   int i,n;
   int ind[MAXN+1];
   if(G[nod].size()==0){
       nr[nod]=v[nod];
       dp[nod]=v[nod];
   }
   else{
     n=G[nod].size();
     nr[nod]=v[nod];
     for(i=0;i<n;i++){
        DFS(G[nod][i]);
        ind[i+1]=G[nod][i];
        nr[nod]+=nr[G[nod][i]];
     }
     std::sort(ind+1,ind+n+1,cmp);
     for(i=1;i<=n;i++)
        dp[nod]+=dp[ind[i]]+(i-1)*nr[ind[i]];
     dp[nod]+=nr[nod];
   }
}
int main(){
   FILE*fi,*fout;
   int i,n,x;
   fi=fopen("dosare.in" ,"r");
   fout=fopen("dosare.out" ,"w");
   fscanf(fi,"%d " ,&n);
   for(i=2;i<=n;i++){
      fscanf(fi,"%d " ,&x);
      G[x].push_back(i);
   }
   for(i=1;i<=n;i++)
     fscanf(fi,"%d " ,&v[i]);
   DFS(1);
   fprintf(fout,"%lld" ,dp[1]);
   fclose(fi);
   fclose(fout);
   return 0;
}