F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
Problem 5077. -- [Ctsc2016]时空旅行

5077: [Ctsc2016]时空旅行

Time Limit: 60 Sec  Memory Limit: 256 MB
Submit: 88  Solved: 20
[Submit][Status][Discuss]

Description

2045年,人类的技术突飞猛进,已经找到了进行时空旅行的方法。小R得到了一台时空旅行仪,他想用它调查不同
时空中人类的发展状况。根据平行时空理论,宇宙中存在着很多独立的时空,每个时空在下一个时间点还会分化出
若干个不同的时空。宇宙是一个三维空间,人类使用空间直角坐标系来描述空间中的一个位置,三维坐标分别是 x
,y,z。我们假设在初始的时空(编号为 0)中,人类存在于地球上(地球的坐标为 (0,0,0)),其它的时空都是从
一个现有的时空发展而来。一个时空发生一个事件之后会发展成为另外一个时空(原来的时空不发生任何变化)。
会影响小R的事件包括两类:人类殖民了一个新的星球,该星球的状态变成"已被殖民";人类放弃了一个已被殖民
的星球,该星球的状态变成"未被殖民"。每次进行时空旅行时,小R会先选定一个时空。在这个时空中,人类已经
殖民了一些星球。小R只要到达该时空中任意一个已被殖民的星球,就能调查人类的发展状况。小R的时空旅行仪出
现了一些问题,调整 x 坐标的按钮坏掉了,因此到达点的 x 坐标被固定了(每次旅行的 x 坐标值可能不同)。
与此同时,他仍能任意调整到达点的 y 坐标和 z 坐标。这个问题大大增大了小R的花费:因为时空旅行没有花费
,但在太空中航行却需要花钱;同时,在不同的星球进行调查也可能会产生不同的费用。假设小R将时空旅行的终
点设为 A,他要进行调查的星球为 B:如果 A 与 B 的欧几里德距离为 d,那么他太空航行的花费就为 d^2;又如
果星球 B 上进行调查的费用为 c,那么小R此次调查的总花费就为 d^2+c。现在给定小R每次旅行到达的时空以及
时空旅行仪上固定的 x 坐标值,请你计算出小R每次旅行完成调查的最小总花费。

Input

输入的第一行包含三个非负整数 n,m,c_0,
n 表示平行时空数量,这些平行时空的编号为 0 到 n-1 的整数,初始时空的编号为 0。
m 表示小R进行的时空旅行的次数,
c_0 表示在地球进行调查的花费。保证 n,m 是正整数,0≤c_0≤10^12。
接下来 n-1 行,依次描述平行时空 1 到 n-1,其中第 i 行分两种情况:
0 fr id x y z c:表示编号为 i 的平行时空由编号为 fr 的时空发展而来,数据保证人类殖民了一个编号为 id 的星球,
该星球的坐标为 (x,y,z),在该星球进行调查的花费为 c。
数据保证给出的星球编号不重复,且 0<id<n;保证 |x|,|y|,|z|≤10^6,0≤c≤10^12。
1 fr id:表示编号为 i 的平行时空由编号为 fr 的时空发展而来,人类放弃了编号为 id 的星球。
数据保证该星球在编号为 fr 的时空中处于被殖民的状态;保证 id>0,即地球一定不会被放弃。
上述两种情况中,各参数均为整数,相邻整数之间均用一个空格隔开;均保证 0≤fr<i。保证不会出现上述两种之外的情况。
接下来 m 行,每行表示小R进行的一次时空旅行。
每行包括 2 个整数 s 和 x_0,表示小R到编号为 s 的平行时空进行了一次时空旅行,时空旅行仪上的 x 坐标被固定为了 x_0。
保证 0≤s<n,|x_0 |≤10^6。
N,M<=5*10^5

Output

输出 m 行,分别表示每次旅行完成调查的最小总花费。

Sample Input

4 4 2
0 0 1 8 2 3 7
0 1 2 10 1 6 2
1 1 1
1 4
2 8
2 6
3 8

Sample Output

18
6
11
66

HINT

Source

[Submit][Status][Discuss]

HOME Back