Pagini recente » Cod sursa (job #2717722) | Cod sursa (job #47774) | Cod sursa (job #990448) | Cod sursa (job #2572715) | Cod sursa (job #198163)
Cod sursa(job #198163)
#include <cstdio>
#include <vector>
#include <algorithm>
#define IN "dosare.in"
#define OUT "dosare.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 16001
#define pb push_back
#define ll long long
using namespace std;
vector < vector<int> > a(N_MAX);
int tata[N_MAX];
int prior[N_MAX];
int acces[N_MAX];
int total[N_MAX];
int stv[N_MAX];
bool marg[N_MAX];
int niv,N;
void scan()
{
freopen(IN, "r",stdin);
freopen(OUT, "w",stdout);
scanf("%d\n", &N);
tata[1]=0;
FOR(i,2,N)
{
scanf("%d\n", &tata[i]);
a[tata[i]].pb(i);
marg[tata[i]] = 1;
}
FOR(i,1,N)
scanf("%d", &acces[i]);
FOR(i,1,N)
total[i] = -1;
}
void see_for(int nod)
{
nod = stv[nod];
if(total[nod] !=-1)
return;
int suma=0,l=a[nod].size();
FOR(i,0,l-1)
if(total[ a[nod][i] ] == -1)
return;
else
suma += total[ a[nod][i] ];
total[nod] = suma + acces[nod];
if(tata[nod] != 0)
stv[++niv] = tata[nod];
}
bool comp (const int &x, const int &y)
{
return total[x] > total[y];
}
void solve()
{
niv=0;
FOR(i,1,N)
if(!marg[i])
stv[++niv] = i;
FOR(i,1,niv)
see_for(i);
FOR(i,1,N)
sort(a[i].begin(),a[i].end() ,comp);
FOR(i,1,N)
{
int l=a[i].size();
FOR(j,0,l-1)
prior[a[i][j]] = j;
}
niv=1;
stv[1] = 1;
total[1] = 1;
FOR(i,1,niv)
{
int l=a[i].size();
FOR(j,0,l-1)
{
int nod = a[i][j];
stv[++niv] = nod;
total[ nod ] = total[ tata[nod] ] + prior[nod] + 1;
}
}
}
void print()
{
ll suma=0;
FOR(i,1,N)
suma += (ll)acces[i] * total[i];
printf("%lld\n",suma);
}
int main()
{
scan();
solve();
print();
return 0;
}