package contest210528; import java.io.*; import java.util.*; import java.util.function.IntUnaryOperator; import java.util.function.LongUnaryOperator; public class H { InputStream is; FastWriter out; String INPUT = ""; public void solve() { int n = ni(); int[] par = new int[n]; Arrays.fill(par, -1); for(int i = 1;i < n;i++){ par[i] = ni()-1; } int[] a = na(n); int[] b = na(n); int[][] g = parentToG(par); int[][] pars = parents(g, 0); int[] ord = pars[1]; Node[] dp = new Node[n]; for(int i = n-1;i >= 0;i--){ int cur = ord[i]; Node ch = null; for(int e : g[cur]){ if(par[cur] == e)continue; ch = dpmerge(ch, dp[e]); } // tr(cur, toString(ch, "")); dp[cur] = dpinsert(ch, new Node(a[cur], b[cur])); // tr(cur, toString(dp[cur], "")); } long ans = 0; for(Node node : nodes(dp[0])){ ans = Math.max(ans, node.v); } out.println(ans); } Node dpmerge(Node A, Node B) { if(count(A) > count(B)){ Node d = A; A = B; B = d; } int pr = 0; while(A != null){ Node[] fe = split(A, 1); Node first = fe[0]; A = fe[1]; int lb = lowerBound(B, first.id); add(B, pr, lb, first.v); if(lb < count(B)) { Node ne = get(B, lb); first.v += ne.v; } B = insert(B, lb, first); while(lb > 0 && get(B, lb-1).v <= first.v){ B = erase(B, lb-1); lb--; } pr = lb + 1; // tr(toString(B, "")); } return B; } Node dpinsert(Node root, Node plus) { int lb = lowerBound(root, plus.id); if(lb < count(root)){ Node ne = get(root, lb); plus.v += ne.v; update(plus); } root = insert(root, lb, plus); while(lb > 0 && get(root, lb-1).v <= plus.v){ root = erase(root, lb-1); lb--; } return root; } public static int lowerBound(Node a, int q) { int lcount = 0; while(a != null){ if(a.id >= q){ a = a.left; }else{ lcount += count(a.left) + 1; a = a.right; } } return lcount; } public static int[][] parentToG(int[] par) { int n = par.length; int[] ct = new int[n]; for(int i = 0;i < n;i++){ if(par[i] >= 0){ ct[i]++; ct[par[i]]++; } } int[][] g = new int[n][]; for(int i = 0;i < n;i++){ g[i] = new int[ct[i]]; } for(int i = 0;i < n;i++){ if(par[i] >= 0){ g[par[i]][--ct[par[i]]] = i; g[i][--ct[i]] = par[i]; } } return g; } public static int[][] parents(int[][] g, int root) { int n = g.length; int[] par = new int[n]; Arrays.fill(par, -1); int[] depth = new int[n]; depth[0] = 0; int[] q = new int[n]; q[0] = root; for (int p = 0, r = 1; p < r; p++) { int cur = q[p]; for (int nex : g[cur]) { if (par[cur] != nex) { q[r++] = nex; par[nex] = cur; depth[nex] = depth[cur] + 1; } } } return new int[][]{par, q, depth}; } public static Random gen = new Random(114514); static public class Node { public int id; public long v; // value public long priority; public Node left, right, parent; public int count; public long add; public long sum; public Node(int id, long v) { this.id = id; this.v = v; priority = gen.nextLong(); update(this); } @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("Node [v="); builder.append(v); builder.append(", id="); builder.append(id); builder.append(", count="); builder.append(count); builder.append(", parent="); builder.append(parent != null ? parent.v : "null"); builder.append(", add="); builder.append(add); builder.append(", sum="); builder.append(sum); builder.append("]"); return builder.toString(); } } public static Node update(Node a) { if(a == null)return null; a.count = 1; if(a.left != null)a.count += a.left.count; if(a.right != null)a.count += a.right.count; a.sum = a.v + a.add * a.count; if(a.left != null)a.sum += a.left.sum; if(a.right != null)a.sum += a.right.sum; return a; } public static Node disconnect(Node a) { if(a == null)return null; a.left = a.right = a.parent = null; return update(a); } public static Node root(Node x) { if(x == null)return null; while(x.parent != null)x = x.parent; return x; } public static int count(Node a) { return a == null ? 0 : a.count; } public static void setParent(Node a, Node par) { if(a != null)a.parent = par; } public static long sum(Node a, int L, int R) { if(a == null || L >= R || L >= count(a) || R <= 0)return 0L; if(L <= 0 && R >= count(a)){ return a.sum; }else{ long ret = 0; ret += sum(a.left, L, R); ret += sum(a.right, L-count(a.left)-1, R-count(a.left)-1); if(L <= count(a.left) && count(a.left) < R)ret += a.v; ret += (Math.min(R, a.count) - L) * a.add; return ret; } } public static void add(Node a, int L, int R, long V) { if(a == null || L >= R || L >= count(a) || R <= 0)return; if(L <= 0 && R >= count(a)){ a.add += V; }else{ add(a.left, L, R, V); add(a.right, L-count(a.left)-1, R-count(a.left)-1, V); if(L <= count(a.left) && count(a.left) < R)a.v += V; } update(a); } public static void fall(Node a) { if(a == null)return; a.v += a.add; if(a.left != null){ a.left.add += a.add; update(a.left); } if(a.right != null){ a.right.add += a.add; update(a.right); } a.add = 0; update(a); } public static Node merge(Node a, Node b) { if(b == null)return a; if(a == null)return b; if(a.priority > b.priority){ fall(a); setParent(a.right, null); setParent(b, null); a.right = merge(a.right, b); setParent(a.right, a); return update(a); }else{ fall(b); setParent(a, null); setParent(b.left, null); b.left = merge(a, b.left); setParent(b.left, b); return update(b); } } // [0,K),[K,N) public static Node[] split(Node a, int K) { if(a == null)return new Node[]{null, null}; fall(a); if(K <= count(a.left)){ setParent(a.left, null); Node[] s = split(a.left, K); a.left = s[1]; setParent(a.left, a); s[1] = update(a); return s; }else{ setParent(a.right, null); Node[] s = split(a.right, K-count(a.left)-1); a.right = s[0]; setParent(a.right, a); s[0] = update(a); return s; } } public static Node insert(Node a, int K, Node b) { if(a == null)return b; fall(a); if(b.priority < a.priority){ if(K <= count(a.left)){ a.left = insert(a.left, K, b); setParent(a.left, a); }else{ a.right = insert(a.right, K-count(a.left)-1, b); setParent(a.right, a); } return update(a); }else{ Node[] ch = split(a, K); b.left = ch[0]; b.right = ch[1]; setParent(b.left, b); setParent(b.right, b); return update(b); } } public static Node insertb(Node root, Node x) { int ind = search(root, x.id); if(ind < 0){ // insert ind = -ind-1; return insert(root, ind, x); }else{ // add Node t = get(root, ind); t.v += x.v; while(t != null){ update(t); t = t.parent; } return root; } } // delete K-th public static Node erase(Node a, int K) { if(a == null)return null; if(K < count(a.left)){ a.left = erase(a.left, K); setParent(a.left, a); return update(a); }else if(K == count(a.left)){ fall(a); setParent(a.left, null); setParent(a.right, null); Node aa = merge(a.left, a.right); disconnect(a); return aa; }else{ a.right = erase(a.right, K-count(a.left)-1); setParent(a.right, a); return update(a); } } public static Node get(Node a, int K) { while(a != null){ fall(a); if(K < count(a.left)){ a = a.left; }else if(K == count(a.left)){ break; }else{ K = K - count(a.left)-1; a = a.right; } } return a; } public static int search(Node a, int q) { int lcount = 0; while(a != null){ fall(a); if(a.id == q){ lcount += count(a.left); break; } if(q < a.id){ a = a.left; }else{ lcount += count(a.left) + 1; a = a.right; } } return a == null ? -(lcount+1) : lcount; } public static int index(Node a) { if(a == null)return -1; int ind = count(a.left); while(a != null){ Node par = a.parent; if(par != null && par.right == a){ ind += count(par.left) + 1; } a = par; } return ind; } public static Node[] nodes(Node a) { return nodes(a, new Node[count(a)], 0, count(a)); } public static Node[] nodes(Node a, Node[] ns, int L, int R) { if(a == null)return ns; fall(a); nodes(a.left, ns, L, L+count(a.left)); ns[L+count(a.left)] = a; nodes(a.right, ns, R-count(a.right), R); return ns; } public static String toString(Node a, String indent) { if(a == null)return ""; StringBuilder sb = new StringBuilder(); sb.append(toString(a.left, indent + " ")); sb.append(indent).append(a).append("\n"); sb.append(toString(a.right, indent + " ")); return sb.toString(); } public static void main(String[] args) { new H().run(); } public void run() { long S = System.currentTimeMillis(); is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new FastWriter(System.out); solve(); out.flush(); long G = System.currentTimeMillis(); tr(G-S+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } private boolean eof() { if(lenbuf == -1)return true; int lptr = ptrbuf; while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false; try { is.mark(1000); while(true){ int b = is.read(); if(b == -1){ is.reset(); return true; }else if(!isSpaceChar(b)){ is.reset(); return false; } } } catch (IOException e) { return true; } } private final byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } // private boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } public static class FastWriter { private static final int BUF_SIZE = 1<<13; private final byte[] buf = new byte[BUF_SIZE]; private final OutputStream out; private int ptr = 0; private FastWriter(){out = null;} public FastWriter(OutputStream os) { this.out = os; } public FastWriter(String path) { try { this.out = new FileOutputStream(path); } catch (FileNotFoundException e) { throw new RuntimeException("FastWriter"); } } public FastWriter write(byte b) { buf[ptr++] = b; if(ptr == BUF_SIZE)innerflush(); return this; } public FastWriter write(char c) { return write((byte)c); } public FastWriter write(char[] s) { for(char c : s){ buf[ptr++] = (byte)c; if(ptr == BUF_SIZE)innerflush(); } return this; } public FastWriter write(String s) { s.chars().forEach(c -> { buf[ptr++] = (byte)c; if(ptr == BUF_SIZE)innerflush(); }); return this; } private static int countDigits(int l) { if (l >= 1000000000) return 10; if (l >= 100000000) return 9; if (l >= 10000000) return 8; if (l >= 1000000) return 7; if (l >= 100000) return 6; if (l >= 10000) return 5; if (l >= 1000) return 4; if (l >= 100) return 3; if (l >= 10) return 2; return 1; } public FastWriter write(int x) { if(x == Integer.MIN_VALUE){ return write((long)x); } if(ptr + 12 >= BUF_SIZE)innerflush(); if(x < 0){ write((byte)'-'); x = -x; } int d = countDigits(x); for(int i = ptr + d - 1;i >= ptr;i--){ buf[i] = (byte)('0'+x%10); x /= 10; } ptr += d; return this; } private static int countDigits(long l) { if (l >= 1000000000000000000L) return 19; if (l >= 100000000000000000L) return 18; if (l >= 10000000000000000L) return 17; if (l >= 1000000000000000L) return 16; if (l >= 100000000000000L) return 15; if (l >= 10000000000000L) return 14; if (l >= 1000000000000L) return 13; if (l >= 100000000000L) return 12; if (l >= 10000000000L) return 11; if (l >= 1000000000L) return 10; if (l >= 100000000L) return 9; if (l >= 10000000L) return 8; if (l >= 1000000L) return 7; if (l >= 100000L) return 6; if (l >= 10000L) return 5; if (l >= 1000L) return 4; if (l >= 100L) return 3; if (l >= 10L) return 2; return 1; } public FastWriter write(long x) { if(x == Long.MIN_VALUE){ return write("" + x); } if(ptr + 21 >= BUF_SIZE)innerflush(); if(x < 0){ write((byte)'-'); x = -x; } int d = countDigits(x); for(int i = ptr + d - 1;i >= ptr;i--){ buf[i] = (byte)('0'+x%10); x /= 10; } ptr += d; return this; } public FastWriter write(double x, int precision) { if(x < 0){ write('-'); x = -x; } x += Math.pow(10, -precision)/2; // if(x < 0){ x = 0; } write((long)x).write("."); x -= (long)x; for(int i = 0;i < precision;i++){ x *= 10; write((char)('0'+(int)x)); x -= (int)x; } return this; } public FastWriter writeln(char c){ return write(c).writeln(); } public FastWriter writeln(int x){ return write(x).writeln(); } public FastWriter writeln(long x){ return write(x).writeln(); } public FastWriter writeln(double x, int precision){ return write(x, precision).writeln(); } public FastWriter write(int... xs) { boolean first = true; for(int x : xs) { if (!first) write(' '); first = false; write(x); } return this; } public FastWriter write(long... xs) { boolean first = true; for(long x : xs) { if (!first) write(' '); first = false; write(x); } return this; } public FastWriter write(IntUnaryOperator f, int... xs) { boolean first = true; for(int x : xs) { if (!first) write(' '); first = false; write(f.applyAsInt(x)); } return this; } public FastWriter write(LongUnaryOperator f, long... xs) { boolean first = true; for(long x : xs) { if (!first) write(' '); first = false; write(f.applyAsLong(x)); } return this; } public FastWriter writeln() { return write((byte)'\n'); } public FastWriter writeln(int... xs) { return write(xs).writeln(); } public FastWriter writeln(long... xs) { return write(xs).writeln(); } public FastWriter writeln(IntUnaryOperator f, int... xs) { return write(f, xs).writeln(); } public FastWriter writeln(LongUnaryOperator f, long... xs) { return write(f, xs).writeln(); } public FastWriter writeln(char[] line) { return write(line).writeln(); } public FastWriter writeln(char[]... map) { for(char[] line : map)write(line).writeln();return this; } public FastWriter writeln(String s) { return write(s).writeln(); } private void innerflush() { try { out.write(buf, 0, ptr); ptr = 0; } catch (IOException e) { throw new RuntimeException("innerflush"); } } public void flush() { innerflush(); try { out.flush(); } catch (IOException e) { throw new RuntimeException("flush"); } } public FastWriter print(byte b) { return write(b); } public FastWriter print(char c) { return write(c); } public FastWriter print(char[] s) { return write(s); } public FastWriter print(String s) { return write(s); } public FastWriter print(int x) { return write(x); } public FastWriter print(long x) { return write(x); } public FastWriter print(double x, int precision) { return write(x, precision); } public FastWriter println(char c){ return writeln(c); } public FastWriter println(int x){ return writeln(x); } public FastWriter println(long x){ return writeln(x); } public FastWriter println(double x, int precision){ return writeln(x, precision); } public FastWriter print(int... xs) { return write(xs); } public FastWriter print(long... xs) { return write(xs); } public FastWriter print(IntUnaryOperator f, int... xs) { return write(f, xs); } public FastWriter print(LongUnaryOperator f, long... xs) { return write(f, xs); } public FastWriter println(int... xs) { return writeln(xs); } public FastWriter println(long... xs) { return writeln(xs); } public FastWriter println(IntUnaryOperator f, int... xs) { return writeln(f, xs); } public FastWriter println(LongUnaryOperator f, long... xs) { return writeln(f, xs); } public FastWriter println(char[] line) { return writeln(line); } public FastWriter println(char[]... map) { return writeln(map); } public FastWriter println(String s) { return writeln(s); } public FastWriter println() { return writeln(); } } public static void trnz(int... o) { for(int i = 0;i < o.length;i++)if(o[i] != 0)System.out.print(i+":"+o[i]+" "); System.out.println(); } // print ids which are 1 public static void trt(long... o) { Queue stands = new ArrayDeque<>(); for(int i = 0;i < o.length;i++){ for(long x = o[i];x != 0;x &= x-1)stands.add(i<<6|Long.numberOfTrailingZeros(x)); } System.out.println(stands); } public static void tf(boolean... r) { for(boolean x : r)System.out.print(x?'#':'.'); System.out.println(); } public static void tf(boolean[]... b) { for(boolean[] r : b) { for(boolean x : r)System.out.print(x?'#':'.'); System.out.println(); } System.out.println(); } public void tf(long[]... b) { if(INPUT.length() != 0) { for (long[] r : b) { for (long x : r) { for (int i = 0; i < 64; i++) { System.out.print(x << ~i < 0 ? '#' : '.'); } } System.out.println(); } System.out.println(); } } public void tf(long... b) { if(INPUT.length() != 0) { for (long x : b) { for (int i = 0; i < 64; i++) { System.out.print(x << ~i < 0 ? '#' : '.'); } } System.out.println(); } } private void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }