题解

题目描述

在微服务部署发布时，通常需要部署所有的现网局点。局点的部署过程存在依赖关系，因为某些局点需要等其他的局点部署完成后，才能开始部署。另外这些局点由于网络或地理位置的原因，所花费的部署时间有可能是不同的。给定一个大小为 n 的数组 region 存储局点之间的部署依赖关系，其中 region[i] 是第 i 个局点的依赖局点，0 <= i < n，-1 <= region[i] < n，-1 表示第 i 个局点没有依赖局点，不需要等待其他局点部署完成才能开始。同时给定一个大小为 n 的数组 time，time[i] 表示部署第 i 个局点所耗费的时间。请返回部署完所有现网局点所耗费的时间。

输入描述

• 输入共 3 行
  • 首行是一个正整数 n，表示输入的局点数量

题目内容

在微服务部署发布时，通常需要部署所有的现网局点。局点的部署过程存在依赖关系，因为某些局点需要等其他的局点部署完成后，才能开始部署。另外这些局点由于网络或地理位置的原因，所花费的部署时间有可能是不同的。给定一个大小为 $n$ 的数组 $region$ 存储局点之间的部署依赖关系，其中 $region[i]$ 是第 $i$ 个局点的依赖局点，$0<=i<n，-1<=region[i]<n$，$-1$ 表示第 $i$ 个局点没有依赖局点，不需要等待其他局点部署完成才能开始。同时给定一个大小为 $n$ 的数组 $time$，$time[i]$ 表示部署第 $i$ 个局点所耗费的时间(分钟),$0<=i<n,0<time[i] <= 1000$。请返回部署完所有现网局点所耗费的时间(分钟)。

输入描述

输入共 $3$ 行

首行是一个正整数 $n$ ，表示输入的局点数量

第二行包含 $n$ 个整数，以空格分离，表示为每个局点 $region$ 父节点下标

第三行包含 $n$ 个整数，以空格分离，表示为每个局点部署的具体时间

数据范围：$1<=n<=1000,-1<=region[i]<=999,0<time[i]<=1000$

输出描述

返回所有局点部署完成的时间

样例1

输入

6
2 2 -1 2 2 2 
3 7 2 1 5 4

输出

9

说明

当前存在 $6$ 个节点，节点 $2$ 是每个节点的父节点，第二行为每个节点的单独部署时间。

第一层节点 $2$ 部署时间最长为 $2$ ，第二层节点 $1$ 部署时间最长为 $7$ ，耗时最长的部署链路为 $2-》7$，最长部署时间为 $9$ ;在 $9$ 分钟内所有局点可部署完

样例2

输入

5
3 -1 3 1 2
5 2 1 4 3

输出

11

说明

当前存在 $5$ 个节点，节点 $0$，$2$ 父节点为 $3$ ，节点 $1$ 为根节点，节点 $4$ 父节点为 $2$ ，第二行为每个节点的单独部署时间。最长部署链路为 $1-》3-》0$，最长部署时间为 $11$ 分钟