Cod sursa(job #124514)

Utilizator swift90Ionut Bogdanescu swift90 Data 19 ianuarie 2008 15:13:00
Problema Dosare Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
int par[16100],ap[16100],fol[16100];
int fi[16100],s[16100];
long long sol;
pair<int, int> aux[16100];
int main(){
	freopen("dosare.in","r",stdin);
	freopen("dosare.out","w",stdout);
	int n,i,j,poz;
	
	scanf("%d",&n);
	for(i=2;i<=n;++i){
		scanf("%d",&par[i]);
		++fi[par[i]];
	}
	scanf("%d",&ap[1]);
	fol[1]=ap[1];
	for(i=2;i<=n;++i){
		scanf("%d",&ap[i]);
		fol[par[i]]+=ap[i];
		++fol[i];
	}
	s[1]=1;
	for(i=1;i<=n;++i){
		if(fi[i]){
			poz=0;
			for(j=i+1;j<=n && poz<fi[i];++j){
				if(par[j]==i){
					aux[poz].first=fol[j];
					aux[poz++].second=j;
				}
			}
			sort(aux,aux+poz);
			--poz;
			for(j=poz;j>=0;--j)
				s[aux[j].second]=((poz-j+1)+s[i]);
			
			for(j=0;j<=poz;++j)
				aux[j].first=aux[j].second=0;
		}
	}
	for(i=1;i<=n;++i)
		sol+=((long long)s[i])*ap[i];
	printf("%lld\n",sol);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}