QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB
[-2]

# 8754. DFS 序

Statistics

题目描述

给定一棵 n 个点的有根树,1 号点为根。每个点有一个权值 wi

求一个最优的 DFS 序使得 ni=1piwi 最大。其中 pi 表示访问第 i 个点的时刻,即第一次访问节点 i 之前访问过多少个不同的节点(包含节点 i 本身)。

输入格式

从标准输入读入数据。

第一行一个正整数 n(1n2×105)

第二行 n 个正整数,其中第 i 个表示 wi(1wi108)

第三行 n1 个正整数,其中第 i 个表示 i+1 号节点的父亲,保证取值在 1i 之间。

输出格式

输出到标准输出。

一行一个整数,表示最大的 ni=1piwi

样例

输入

5
8 5 3 6 4
1 1 3 3

输出

75

解释

按照 (1,3,5,4,2) 的访问顺序可以取得最大值 1×8+2×3+3×4+4×6+5×5=75

注意 (1,3,2,4,5) 不是一个合法的访问顺序。