Post Tree

Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given a rooted tree on N vertices. The nodes are numbered from 1 to N, and Node 1 is the root. Each node u has an associated value attached to it: A_{u}.
For each vertex v, we consider the path going upwards from v to the root. Suppose that path is v_{1}, v_{2}, .., v_{k}, where v_{1} = v and v_{k} = 1. The cost of any node on this path is equal to the minimum value among all the nodes to its left in the path sequence, including itself. That is, cost(v_{i}) = min_{1 <= j <= i}{A_{vj}}. And the cost of the path is the sum of costs of all the nodes in it.
For every node in the tree, find the cost of the path from that node to the root.
Input
 The first line of the input contains a single integer, N, denoting the number of nodes in the tree.
 The next line contains N1 integers, the ith of which denotes the parent of node i+1.
 The next line contains N integers, the ith of which denotes A_{i}.
Output
Output a single line containing N integers, the ith of which should be the cost of the path from node i to the root.
Constraints
 1 ≤ N ≤ 100,000
 1,000,000,000 ≤ A_{v} ≤ 1,000,000,000
Subtasks
 Subtask #1 (30 points): 1 ≤ N ≤ 2000
 Subtask #2 (70 points): Original constraints.
Example
Input: 8 1 1 1 1 5 8 6 1 2 3 4 5 15 70 10 Output: 1 3 4 5 6 21 96 26
Explanation
For example, take a look at the path from vertex 7: The path is 7 > 8 > 6 > 5 > 1.
Cost(7) has no choice but to be A_{7}. So Cost(7) = 70.
Cost(8) will be minimum of A_{7} and A_{8}, which turns out to be A_{8}. So Cost(8) = 10.
Cost(6) = minimum {A_{7}, A_{8}, A_{6}} = minimum {70, 10, 15} = 10.
Cost(5) = minimum {70, 10, 15, 5} = 5.
Cost(1) = minimum {70, 10, 15, 5, 1} = 1.
So, the cost of the path from 7 to the root is 70 + 10 + 10 + 5 + 1 = 96.
Author:  gainullinildar 
Tester:  melfice 
Editorial  https://discuss.codechef.com/problems/POSTTREE 
Tags  dfs, easymedium, gainullinildar, lca, ltime48 
Date Added:  26052017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions