Pagini recente » Cod sursa (job #161551) | Cod sursa (job #1153114) | Cod sursa (job #1723970) | Cod sursa (job #1123066) | Cod sursa (job #1383541)
#include <stdio.h>
#define MAXN 16000
int fr[MAXN], fr2[MAXN], nod[MAXN], next[MAXN], ult[MAXN], v[MAXN];
long long rez;
void prec(int x){
int poz = ult[x];
while(poz > -1){
prec(nod[poz]);
fr2[x] += fr2[nod[poz]];
poz = next[poz];
}
fr2[x] += fr[x];
}
void qs(int st, int dr){
int i = st, j = dr, piv = v[(st + dr) / 2], aux;
while(i <= j){
while(fr2[v[i]] > fr2[piv])
i++;
while(fr2[v[j]] < fr2[piv])
j--;
if(i <= j){
aux = v[i];
v[i] = v[j];
v[j] = aux;
i++;
j--;
}
}
if(st < j)
qs(st, j);
if(i < dr)
qs(i, dr);
}
void bfs(int p, int k, int dp){
int poz, dr = dp;
poz = ult[p];
while(poz != -1){
v[dr] = nod[poz];
dr++;
poz = next[poz];
}
qs(dp, dr - 1);
int i;
for(i = dp; i < dr; i++)
rez += 1LL * (i - dp + 1 + k) * fr[v[i]];
for(i = dp; i < dr; i++)
bfs(v[i], k + i - dp + 1, dr);
}
int main(){
FILE *in = fopen("dosare.in", "r");
int n, i, x;
fscanf(in, "%d", &n);
for(i = 0; i < n; i++)
ult[i] = -1;
for(i = 1; i < n; i++){
fscanf(in, "%d", &x);
nod[i - 1] = i;
next[i - 1] = ult[x - 1];
ult[x - 1] = i - 1;
}
for(i = 0; i < n; i++)
fscanf(in, "%d", &fr[i]);
fclose(in);
rez = fr[0];
prec(0);
bfs(0, 1, 0);
FILE *out = fopen("dosare.out", "w");
fprintf(out, "%lld", rez);
fclose(out);
return 0;
}