题目描述

现给定一棵以 $1$ 号点为根的树，第 $i$ 个点的点权为 $x_i$ ，父节点为 $p_i$（$1$ 号点没有父节点）。请你在树上找到两条没有交集链（一个点也可以是一条链），使得所选中的两条链上的点权之和最大，求满足条件的最大点权和。

输入格式

输入共三行： 第一行，一个正整数 $n$ 第二行，$n-1$ 个整数，表示 $p_2,p_3,\dots,p_n$，其中 $p_i$ 表示结点 $i$ 的父亲，保证 $p_i<i$。 第三行，$n$个正整数，分别表示 $x_1,...,x_n$

输出格式

输出共一个正整数，表示最大点权和。

5
1 1 1 1
1 2 3 4 5

13

样例解释 1

选3号点单独为链，与1、4、5号点组成的链

数据范围

• 对于 $30\%$ 的数据，满足 $2 \leq n \leq 10$
• 对于 $60\%$ 的数据，满足 $2 \leq n \leq 10^3$
• 对于 $100\%$ 的数据，满足 $2 \leq n \leq 10^5, 1\leq x_i \leq 10^9$