#P1003. [2024 GDCPC C] DFS 序
[2024 GDCPC C] DFS 序
Background
Special for beginners, ^_^
Description
给定一棵 个点的有根树, 号点为根。每个点有一个权值 。
求一个最优的 DFS 序使得 最大。其中 表示访问第 个点的时刻,即第一次访问节点 之前访问过多少个不同的节点(包含节点 本身)。
Format
Input
第一行一个正整数 。
第二行 个正整数,其中第 个表示 。
第三行 个正整数,其中第 个表示 号节点的父亲,保证取值在 之间。
Output
一行一个整数,表示最大的 。
Samples
5
8 5 3 6 4
1 1 3 3
75
Note
按照 的访问顺序可以取得最大值 $1\times 8+2\times 3+3\times 4+4\times 6+5\times 5=75$。
注意 不是一个合法的访问顺序。
Limitation
1s, 1024KiB for each test case.
Related
In following contests: