Guest User

Untitled

a guest
Feb 14th, 2016
174
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.OutputStream;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.PrintWriter;
  5. import java.util.Arrays;
  6. import java.io.IOException;
  7. import java.io.InputStreamReader;
  8. import java.util.ArrayList;
  9. import java.util.StringTokenizer;
  10. import java.io.BufferedReader;
  11. import java.util.Collections;
  12. import java.io.InputStream;
  13.  
  14. /**
  15.  * Built using CHelper plug-in
  16.  * Actual solution is at the top
  17.  */
  18. public class Main {
  19.     public static void main(String[] args) {
  20.         InputStream inputStream = System.in;
  21.         OutputStream outputStream = System.out;
  22.         InputReader in = new InputReader(inputStream);
  23.         PrintWriter out = new PrintWriter(outputStream);
  24.         TaskH solver = new TaskH();
  25.         solver.solve(1, in, out);
  26.         out.close();
  27.     }
  28.  
  29.     static class TaskH {
  30.         static final long INF = (long) 1e18;
  31.         int n;
  32.         int[] parent;
  33.         int[] a;
  34.         long[][] best;
  35.         int[][] k;
  36.         ArrayList<Integer> order;
  37.         ArrayList<Integer>[] g;
  38.  
  39.         public void solve(int testNumber, InputReader in, PrintWriter out) {
  40.             n = in.nextInt();
  41.             g = new ArrayList[n];
  42.             for (int i = 0; i < n; ++i)
  43.                 g[i] = new ArrayList<>();
  44.             a = new int[n];
  45.             for (int i = 0; i < n; ++i) {
  46.                 a[i] = in.nextInt();
  47.             }
  48.             parent = new int[n];
  49.             parent[0] = -1;
  50.             for (int i = 1; i < n; ++i) {
  51.                 parent[i] = in.nextInt() - 1;
  52.                 g[parent[i]].add(i);
  53.             }
  54.             best = new long[n][n];
  55.             k = new int[n][n];
  56.             for (int i = 0; i < n; ++i) {
  57.                 Arrays.fill(best[i], INF);
  58.                 Arrays.fill(k[i], -1);
  59.                 best[i][i] = a[i];
  60.                 k[i][i] = i;
  61.             }
  62.  
  63.             order = new ArrayList<>();
  64.             dfs(0);
  65.  
  66.             int[] prevKid = new int[n];
  67.             Arrays.fill(prevKid, -1);
  68.             int[] brother = new int[n];
  69.             Arrays.fill(brother, -1);
  70.             int[] depth = new int[n];
  71.             for (int i : order) {
  72.                 if (i == 0) continue;
  73.                 brother[i] = prevKid[parent[i]];
  74.                 prevKid[parent[i]] = i;
  75.                 depth[i] = depth[parent[i]] + 1;
  76.             }
  77.  
  78.             for (int i : order) {
  79.                 if (i == 0) continue;
  80.                 // p[i] -> i
  81.  
  82.                 long sum = a[i];
  83.  
  84.                 int x = parent[i];
  85.                 int prevX = i;
  86.                 while (x != -1) {
  87.                     sum += a[x];
  88.                     // d[x][i]
  89.                     // k[x][i - 1] <= k[x][i] <= k[x - 1][i]
  90.  
  91.                     int l = k[x][parent[i]];
  92.                     int r = parent[x] == -1 ? i : k[prevX][i];
  93.                     prevX = x;
  94.                     if (brother[i] != -1) {
  95.                         int brotherL = k[x][brother[i]];
  96.                         if (brotherL == brother[i]) {
  97.                             l = i;
  98.                         } else {
  99.                             if (brotherL != -1 && depth[brotherL] > depth[l])
  100.                                 l = brotherL;
  101.                         }
  102.                     }
  103.  
  104.                     int y = r;
  105.                     while (y != x) {
  106.                         long cur = sum + best[x][parent[y]] + best[y][i];
  107.                         if (cur < best[x][i]) {
  108.                             best[x][i] = cur;
  109.                             k[x][i] = y;
  110.                         }
  111.                         if (y == l) break;
  112.                         y = parent[y];
  113.                     }
  114.  
  115.                     x = parent[x];
  116.                 }
  117.             }
  118.  
  119.             for (int i = 0; i < n; ++i) {
  120.                 out.println(best[0][i]);
  121.             }
  122.         }
  123.  
  124.         private void dfs(int x) {
  125.             order.add(x);
  126.             ArrayList<Pair> kids = new ArrayList<>();
  127.             for (int y : g[x]) {
  128.                 kids.add(new Pair(a[y], y));
  129.             }
  130.             Collections.sort(kids);
  131.             for (Pair kid : kids)
  132.                 dfs(kid.second);
  133.         }
  134.  
  135.         static class Pair implements Comparable<Pair> {
  136.             int first;
  137.             int second;
  138.  
  139.             public Pair(int first, int second) {
  140.                 this.first = first;
  141.                 this.second = second;
  142.             }
  143.  
  144.  
  145.             public int compareTo(Pair o) {
  146.                 if (first != o.first)
  147.                     return Integer.compare(first, o.first);
  148.                 return Integer.compare(second, o.second);
  149.             }
  150.  
  151.         }
  152.  
  153.     }
  154.  
  155.     static class InputReader {
  156.         public BufferedReader reader;
  157.         public StringTokenizer tokenizer;
  158.  
  159.         public InputReader(InputStream stream) {
  160.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  161.             tokenizer = null;
  162.         }
  163.  
  164.         public String next() {
  165.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  166.                 try {
  167.                     tokenizer = new StringTokenizer(reader.readLine());
  168.                 } catch (IOException e) {
  169.                     throw new RuntimeException(e);
  170.                 }
  171.             }
  172.             return tokenizer.nextToken();
  173.         }
  174.  
  175.         public int nextInt() {
  176.             return Integer.parseInt(next());
  177.         }
  178.  
  179.     }
  180. }
RAW Paste Data