题目描述
有一棵包括
对所有结点
下图给出了一个包含
每个结点都被赋以非负整数的权重。我们将结点
你的任务是写一个程序来回答
对树中的每个结点,都指派一个整数,称为系数。这样的指派结果被描述成一个序列
对某个询问
对于一个给定的系数序列
可以证明,对于任意询问,都至少存在一个有效的系数序列。
实现细节
你需要实现如下两个函数:
void init(std::vector<int> P, std::vector<int> W)
, :两个长度为 的整数数组,记录了结点的父结点和权重。- 对于每个测试样例,在评测程序与你的程序开始交互时,该函数将被恰好调用一次。
long long query(int L, int R)
, :两个整数,描述一次询问。- 对于每个测试样例,在
init
被调用后,该函数将被调用 次。 - 该函数应该返回对给定询问的答案。
约束条件
- 对所有满足
的 ,都有 - 对所有满足
的 ,都有 - 在每次询问中,都有
子任务
子任务 | 分数 | 额外的约束条件 |
---|---|---|
1 | ||
2 | ||
3 | ||
4 | 对所有满足 |
|
5 | 对所有满足 |
|
6 | ||
7 | 没有额外的约束条件。 |
例子
考虑如下调用:
init([-1, 0, 0], [1, 1, 1])
这棵树包含
query(1, 1)
本次询问有
对每个结点
结点 | 权重 | 系数 | 代价 |
---|---|---|---|
0 | 1 | -1 | |
1 | 1 | 1 | |
2 | 1 | 1 |
因此总体代价为
query(1, 2)
对于该询问的最小总体代价为
评测程序示例
输入格式:
N P[1] P[2] ... P[N-1] W[0] W[1] ... W[N-2] W[N-1] Q L[0] R[0] L[1] R[1] ... L[Q-1] R[Q-1]
这里的 query
的第
输出格式:
A[0] A[1] ... A[Q-1]
这里的 query
时返回的值。
时间限制:
空间限制: