Cod sursa(job #1430258)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 8 mai 2015 00:43:40
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

#define int long long

vector<int> g[16000];
int a[16000];
int N;

int propaga_in_sus(int u) {
  for(int v : g[u]) {
    a[u] += propaga_in_sus(v);
  }
  return a[u];
}

int f(int u) {
  int s = 0;
  vector<int> r;
  for (int v : g[u]) {
    s += f(v);
    r.push_back(a[v]);
  }
  sort(r.begin(), r.end());
  reverse(r.begin(), r.end());
  for (int i = 0; i < r.size(); ++i) {
    s += i * r[i];
  }
  return s + a[u];
}

#define int int
int main(int argc, char *argv[]) {
#define int long long
  freopen("dosare.in", "r", stdin);
  freopen("dosare.out", "w", stdout);

  scanf("%lld", &N);
  for(int i = 1; i < N; ++i) {
    int tata;
    scanf("%lld", &tata);
    g[tata - 1].push_back(i);
  }
  for(int i = 0; i < N; ++i) {
    int acc;
    scanf("%lld", &acc);
    a[i] = acc;
  }

  propaga_in_sus(0);
  printf("%lld\n", f(0));

  return 0;
}