You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 2.0 秒

空间限制： 512 MB

本题目前依旧在测试调整中...

题目描述

给定一棵 $n$ 个点的有根树，其中节点 $1$ 为根，节点 $i~(2\le i\le n)$ 的父亲为 $f_i$。

有 $n$ 个任务，第 $i$ 个任务的耗时为 $t_i$。你需要将这 $n$ 个任务分配给 $n$ 个节点，满足每个节点恰好完成一个任务。于此同时，每个节点均有一个限制，节点 $i~(1\le i\le n)$ 的限制为 $w_i$，要求在节点 $i$ 的子树内的所有任务的耗时均不能超过 $w_i$。

现在，你可以选择一个节点，并将其的限制增加 $k$，其中 $k$ 为任意非负整数，你需要求出最小的 $k$，使得在增大一个节点的限制后，存在一种任务分配的方案满足所有限制，保证存在至少一种增加限制的方案使得存在一种任务分配的方案满足所有限制。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 task.h。

你需要实现以下函数。

int solve(const std::vector<int>& f, const std::vector<int>& t, const std::vector<int>& w);

请注意以下几点：

• 交互库没有包含万能头，如使用其他库，需要自行引入；
• 交互库没有引入 using namespace std；
• 函数传入的 vector 不可被修改。

其中传入的三个 vector 的规模均为 $n+1$，其中：

• $f_2,\cdots f_n$ 放置在动态数组 f 当中秩为 $2,3,\cdots, n$ 的位置，表示 $2\sim n$ 号节点的父亲；
• $t_1,\cdots t_n$ 放置在动态数组 t 当中秩为 $1,2,\cdots, n$ 的位置，表示每个任务的耗时；
• $w_1,\cdots w_n$ 放置在动态数组 w 当中秩为 $1,2,\cdots, n$ 的位置，表示每个节点的限制；
• 动态数组的开头元素秩为 $0$。

返回的整数即为限制增量的最小值。

以下我们给出一个代码提交实例（会固定返回 $n$，仅作为示例，不保证能得分）：

#include "task.h"
int solve(const std::vector<int>& f, const std::vector<int>& t, const std::vector<int>& w)
{
    int n = f.size() - 1;
    return n;
}

交互库实例

具体请见附加文件区的 interactor.cc 和 task.h。需要注意的是，该白盒交互库并非实际评测使用的交互库。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，输入以下 Linux 命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

6
1 2 2 1 5
1 2 2 3 5 6
6 1 3 3 5 1

2

样例 1 解释

一种可行的方案为：将节点 $2$ 的限制增加 $2$ 后，将耗时为 $6,3,2,2,5,1$ 的任务依次分配给节点 $1\sim 6$。

请注意，本样例并未使用上述提供的白盒交互库。

499998 55815863 1

381079

样例 2 解释

本样例有 $n\le 5\times 10^5$，样例输入输出均遵循上述白盒交互库获得。

3000000 393087878 1

354159

样例 3 解释

本样例有 $n\le 3\times 10^6$，样例输入输出均遵循上述白盒交互库获得。

子任务

对于所有测试数据，保证 $1\le n\le 3\times 10^6,~1\le f_i<i,~1\le t_1\le t_2\le ...\le t_n\le n,~1\le w_i\le n$。保证存在至少一种增加限制的方案使得存在一种任务分配的方案满足所有限制。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

提示

在子任务 8 下，交互库至多需要 500ms 生成输入数据，留给选手解决问题的时限实际只有 500ms。