fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <complex>
  4. #include <vector>
  5. #include <utility>
  6. #include <algorithm>
  7. #include <cassert>
  8. #include <queue>
  9. #include <cstdio>
  10. #include <cstdlib>
  11. #include <cstring>
  12. using namespace std;
  13.  
  14. #define rep(i, n) for (int i = 0; i < (int)(n); i++)
  15.  
  16. int N;
  17. int P[810], D[810];
  18.  
  19. int deg[810];
  20. vector<pair<int, int> > adj[810];
  21.  
  22. pair<int, int> farthest(int v, int p) {
  23.   pair<int, int> res = make_pair(0, v);
  24.   for (const auto &e : adj[v]) {
  25.     if (e.first == p) continue;
  26.     pair<int, int> p = farthest(e.first, v);
  27.     res = max(res, make_pair(p.first + e.second, p.second));
  28.   }
  29.   return res;
  30. }
  31.  
  32. int main() {
  33.   for (;;) {
  34.     scanf("%d", &N);
  35.     if (N == 0) return 0;
  36.  
  37.     memset(deg, 0, sizeof(deg));
  38.     for (int i = 1; i <= N - 1; ++i) {
  39.       scanf("%d", &P[i]);
  40.       --P[i];
  41.       ++deg[i];
  42.       ++deg[P[i]];
  43.     }
  44.     for (int i = 1; i <= N - 1; ++i) {
  45.       scanf("%d", &D[i]);
  46.     }
  47.  
  48.     rep (v, N) adj[v].clear();
  49.     for (int p = 1; p <= N - 1; ++p) {
  50.       int q = P[p];
  51.       if (deg[p] == 1 || deg[q] == 1) continue;
  52.       adj[p].emplace_back(q, D[p]);
  53.       adj[q].emplace_back(p, D[p]);
  54.     }
  55.  
  56.     pair<int, int> p1;
  57.     rep (v, N) {
  58.       if (deg[v] == 1) continue;
  59.       p1 = farthest(v, -1);
  60.       break;
  61.     }
  62.     pair<int, int> p2 = farthest(p1.second, -1);
  63.  
  64.     int S1 = 0, S2 = 0;
  65.     for (int p = 1; p <= N - 1; ++p) {
  66.       int q = P[p];
  67.       S1 += D[p];
  68.       if (deg[p] > 1 && deg[q] > 1) {
  69.         S2 += D[p];
  70.       }
  71.     }
  72.     printf("%d\n", S1 + S2 + S2 - p2.first);
  73.   }
  74. }
  75.  
Success #stdin #stdout 0s 3492KB
comments (?)
stdin
copy 
4
1 2 3
10 20 30
10
1 2 2 1 5 5 1 8 8
10 1 1 20 1 1 30 1 1
3
1 1
1 1
0
stdout
copy 
80
136
2
https://ideone.com/9sN2Bk
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!