Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.OutputStream;
- import java.io.IOException;
- import java.io.InputStream;
- import java.io.PrintWriter;
- import java.util.Arrays;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.ArrayList;
- import java.util.StringTokenizer;
- import java.io.BufferedReader;
- import java.util.Collections;
- import java.io.InputStream;
- /**
- * Built using CHelper plug-in
- * Actual solution is at the top
- */
- public class Main {
- public static void main(String[] args) {
- InputStream inputStream = System.in;
- OutputStream outputStream = System.out;
- InputReader in = new InputReader(inputStream);
- PrintWriter out = new PrintWriter(outputStream);
- TaskH solver = new TaskH();
- solver.solve(1, in, out);
- out.close();
- }
- static class TaskH {
- static final long INF = (long) 1e18;
- int n;
- int[] parent;
- int[] a;
- long[][] best;
- int[][] k;
- ArrayList<Integer> order;
- ArrayList<Integer>[] g;
- public void solve(int testNumber, InputReader in, PrintWriter out) {
- n = in.nextInt();
- g = new ArrayList[n];
- for (int i = 0; i < n; ++i)
- g[i] = new ArrayList<>();
- a = new int[n];
- for (int i = 0; i < n; ++i) {
- a[i] = in.nextInt();
- }
- parent = new int[n];
- parent[0] = -1;
- for (int i = 1; i < n; ++i) {
- parent[i] = in.nextInt() - 1;
- g[parent[i]].add(i);
- }
- best = new long[n][n];
- k = new int[n][n];
- for (int i = 0; i < n; ++i) {
- Arrays.fill(best[i], INF);
- Arrays.fill(k[i], -1);
- best[i][i] = a[i];
- k[i][i] = i;
- }
- order = new ArrayList<>();
- dfs(0);
- int[] prevKid = new int[n];
- Arrays.fill(prevKid, -1);
- int[] brother = new int[n];
- Arrays.fill(brother, -1);
- int[] depth = new int[n];
- for (int i : order) {
- if (i == 0) continue;
- brother[i] = prevKid[parent[i]];
- prevKid[parent[i]] = i;
- depth[i] = depth[parent[i]] + 1;
- }
- for (int i : order) {
- if (i == 0) continue;
- // p[i] -> i
- long sum = a[i];
- int x = parent[i];
- int prevX = i;
- while (x != -1) {
- sum += a[x];
- // d[x][i]
- // k[x][i - 1] <= k[x][i] <= k[x - 1][i]
- int l = k[x][parent[i]];
- int r = parent[x] == -1 ? i : k[prevX][i];
- prevX = x;
- if (brother[i] != -1) {
- int brotherL = k[x][brother[i]];
- if (brotherL == brother[i]) {
- l = i;
- } else {
- if (brotherL != -1 && depth[brotherL] > depth[l])
- l = brotherL;
- }
- }
- int y = r;
- while (y != x) {
- long cur = sum + best[x][parent[y]] + best[y][i];
- if (cur < best[x][i]) {
- best[x][i] = cur;
- k[x][i] = y;
- }
- if (y == l) break;
- y = parent[y];
- }
- x = parent[x];
- }
- }
- for (int i = 0; i < n; ++i) {
- out.println(best[0][i]);
- }
- }
- private void dfs(int x) {
- order.add(x);
- ArrayList<Pair> kids = new ArrayList<>();
- for (int y : g[x]) {
- kids.add(new Pair(a[y], y));
- }
- Collections.sort(kids);
- for (Pair kid : kids)
- dfs(kid.second);
- }
- static class Pair implements Comparable<Pair> {
- int first;
- int second;
- public Pair(int first, int second) {
- this.first = first;
- this.second = second;
- }
- public int compareTo(Pair o) {
- if (first != o.first)
- return Integer.compare(first, o.first);
- return Integer.compare(second, o.second);
- }
- }
- }
- static class InputReader {
- public BufferedReader reader;
- public StringTokenizer tokenizer;
- public InputReader(InputStream stream) {
- reader = new BufferedReader(new InputStreamReader(stream), 32768);
- tokenizer = null;
- }
- public String next() {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- try {
- tokenizer = new StringTokenizer(reader.readLine());
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return tokenizer.nextToken();
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement