Cod sursa(job #2387219)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 24 martie 2019 14:04:41
Problema Dosare Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>

FILE *in = fopen("dosare.in", "r"), *out = fopen("dosare.out", "w") ;

const int MV = 16000  ;

long long s[MV + 1] ;
int dp[MV + 1], a[MV + 1] ;

std::vector <int> graph[MV + 1] ;

long long ans ;

bool cmp(const int &a, const int &b) {
  return s[a] > s[b] ;
}

void union_find(int x) {
  s[x] = a[x] ;
  for (auto &y : graph[x]) {
    union_find(y) ;
    s[x] += s[y] ;
  }
}

void dfs_minim(int x) {
  dp[x]++ ;
  ans += 1LL * a[x] * dp[x] ;
  std::sort(graph[x].begin(), graph[x].end(), cmp) ;
  int i ;
  for (i = 0 ; i < graph[x].size() ; ++ i) {
    dp[graph[x][i]] = dp[x] + i ;
    dfs_minim(graph[x][i]) ;
  }
}

int main() {
  int n, i, x ;
  fscanf(in, "%d", &n) ;
  for (i = 2 ; i <= n ; ++ i) {
    fscanf(in, "%d", &x)  ;
    graph[x].push_back(i) ;
  }
  for (i = 1 ; i <= n ; ++ i) {
    fscanf(in, "%d ", a + i) ;
  }
  union_find(1) ;
  dfs_minim(1) ;
  fprintf(out, "%lld", ans) ;
  return 0 ;
}