2305. [CTSC 2016]时空旅行

【题目描述】

   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每次旅行完成调查的最小总花费。

【输入格式】

输入的第一行包含三个非负整数 n,m,c0，n 表示平行时空数量，这些平行时空的编号为 0 到 n-1 的整数，初始时空的编号为 0。m 表示小R进行的时空旅行的次数，c0表示在地球进行调查的花费。保证 0 < n,m ≤5*10^5，0 ≤ c0 ≤ 10^12。

  接下来 n-1 行，依次描述平行时空 1 到 n-1，其中第 i 行分两种情况：

   ●  0 fr id x y z c：表示编号为 i 的平行时空由编号为 fr 的时空发展而来，数据保证人类殖民了一个编号为 id 的星球，该星球的坐标为(x,y,z)，在该星球进行调查的花费为c。数据保证给出的星球编号不重复，且 O < id < n；保证 |x|,|y|,|z| ≤ 10^6，0 ≤ c ≤ 10^12。

   ●  1 fr id：表示编号为 i 的平行时空由编号为 fr 的时空发展而来，人类放弃了编号为 id 的星球。数据保证该星球在编号为 fr 的时空中处于被殖民的状态；保证 id > 0，即地球一定不会被放弃。

   上述两种情况中，各参数均为整数，相邻整数之间均用一个空格隔开；均保证 O ≤ fr < i。保证不会出现上述两种之外的情况。

   接下来 m 行，每行表示小R进行的一次时空旅行。每行包括 2 个整数 s 和 x0，表示小R到编号为 s 的平行时空进行了一次时空旅行，时空旅行仪上的 x 坐标被固定为了 x0。

【输出格式】

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

【样例输入】

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

【样例输出】

l8
6
11
66

【子任务】

【来源】

CTSC2016 D1T1