Cod sursa(job #423159)

Utilizator swift90Ionut Bogdanescu swift90 Data 23 martie 2010 15:53:53
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> nr[16010];
int N;
long long sol,fol[16010],so[16010];
void solve(int x){
	int v=nr[x].size();
	for(int i=0;i<v;++i){
		so[i]=fol[nr[x][i]];
		fol[x]+=so[i];
	}
	sol+=fol[x];
	sort(so,so+v);
	for(int i=v-1;i>=0;--i)
		sol+=(v-i-1)*so[i];
}
void df(int x){
	for(vector<int>::iterator it=nr[x].begin();it!=nr[x].end();++it)
		df(*it);
	solve(x);
}
int main(){
	freopen("dosare.in","r",stdin);
	freopen("dosare.out","w",stdout);
	int i,x;
	scanf("%d",&N);
	for(i=2;i<=N;++i){
		scanf("%d",&x);
		nr[x].push_back(i);
	}
	for(i=1;i<=N;++i)
		scanf("%lld",&fol[i]);
	df(1);
	
	printf("%lld\n",sol);
	fclose(stdin);
	fclose(stdout);
	return 0;
}