問題文
岩井君经常爬山,是一名专业登山运动员(事实)。今天,岩井君将接受攀登以其奇特形状而闻名的栗山的挑战。
岩井君想要登上桐山山顶。另外,为了欣赏山顶最好的景色,同时减少攀登时消耗的体力,岩井君总是选择最短路线登顶。但雾山山上经常发生山体滑坡,导致道路无法通行。而且,由于这座山无人管理,一旦发生山体滑坡,那条路就再也走不通了。
当岩井先生去爬山时,他会根据迄今为止获得的山体滑坡信息来决定登山路线。由于他获得了按时间顺序排列的山路形状和山体滑坡的信息,因此利用计算机科学的力量告诉他每条信息后可用的最短路线的距离。
課題
N 由顶点和组成的有根树 给出了 Q 查询。每个顶点有 1 从 N 具有整数、顶点 1 是这棵树的根。顶点 i(≧2) 是顶点 父级为 p_i(<i) , 连接 p_i 和 我讨厌 i 的边是成本 有 w_i 。
最初,所有边都可以使用。每个查询都是 (x_i,p_{x_i}) 将来不应使用”,并且在某个查询之前不再可用的边在后续查询中仍然不可用。 执行完每个查询后,从某个叶子的顶点到该顶点 输出直到 1 的路径成本总和的最小值。 如果您无法到达 1 输出 −1 。
制約
所有输入数据满足以下约束。
- 3≦N≦10^5
- 1≦Q≦N−1
- 1≦w_i≦10^3
- 2≦x_i≦N
此外,针对该问题设置了部分点,并且一个点的输入数据另外满足以下约束。 在
- N≦10^3
入力
N Q p_2 w_2 p_3 w_3 : p_N w_N x_1 x_2 : x_Q
出力
i(1≦i≦Q) 行上, 输出第i 条信息后的最短路径的距离。但是,如果你无法到达山顶 输出 -1 。
入力例1
10 5 1 5 2 6 2 3 1 2 5 1 5 8 7 2 7 2 2 9 4 6 3 7 2
出力例1
3 11 12 14 -1
示意图如下。

故事: kyuridenamida, kagamiz
问题: ey429
测试仪: kyuridenamida, kagamiz, japlj
问题: ey429
测试仪: kyuridenamida, kagamiz, japlj