P5416 [CTSC2016] Time-Space Travel

In 2045, human technology advanced rapidly, and people have found a way to travel through time and space. Little R obtained a time-space travel device and wants to use it to investigate the development of humans in different time-spaces. According to the parallel time-space theory, there are many independent time-spaces in the universe. Each time-space will further split into several different time-spaces at the next time point. The universe is a three-dimensional space, and humans use a 3D Cartesian coordinate system to describe a position in space, with coordinates $x, y, z$. Assume that in the initial time-space (numbered $0$), humans live on Earth (Earth’s coordinates are $(0,0,0)$), and all other time-spaces are developed from an existing time-space. After one time step, a time-space will develop into another time-space (the original time-space does not change). Events that affect Little R are of two types: 1. Humans colonize a new planet, and the planet’s state becomes “colonized”. 2. Humans abandon a colonized planet, and the planet’s state becomes “not colonized”. Each time Little R performs time-space travel, he first chooses a time-space. In this time-space, humans have already colonized some planets. As long as Little R reaches any colonized planet in that time-space, he can investigate the development of humans. However, Little R’s device has some problems: the button for adjusting the $x$ coordinate is broken, so the $x$ coordinate of the destination point is fixed (the fixed $x$ value may differ for each trip). At the same time, he can still freely adjust the $y$ and $z$ coordinates of the destination. This greatly increases Little R’s cost: time-space travel itself is free, but traveling in space costs money; also, investigating on different planets may incur different fees. Suppose Little R sets the endpoint of the time-space travel to $A$, and the planet he investigates is $B$. If the Euclidean distance between $A$ and $B$ is $d$, then the cost of space travel is $d^2$. If the investigation fee on planet $B$ is $c$, then the total cost of this investigation is $d^2 + c$. Now you are given the time-space Little R arrives at for each trip and the fixed $x$ coordinate value on the device. Please compute the minimum total cost for Little R to complete the investigation for each trip.

The first line contains three non-negative integers $n, m, c_0$. $n$ is the number of parallel time-spaces, numbered from $0$ to $n-1$, and the initial time-space is numbered $0$. $m$ is the number of time-space trips Little R makes. $c_0$ is the investigation fee on Earth. It is guaranteed that $0 < n, m \leq 5 \times 10^5$, and $0 \leq c_0 \leq 10^{12}$. The next $n-1$ lines describe parallel time-spaces $1$ to $n-1$ in order. For time-space $i$, the $i$-th line is one of the following two cases: 1. $0 \ \mathrm{fr} \ \mathrm{id} \ x \ y \ z \ c$: time-space $i$ develops from time-space $\mathrm{fr}$, and humans colonize a planet with number $\mathrm{id}$. The planet’s coordinates are $(x, y, z)$, and the investigation fee on this planet is $c$. The testdata guarantees that the given planet numbers are all distinct, and $0 < \mathrm{id} < n$. Also, $|x|, |y|, |z| \leq 10^6$, and $0 \leq c \leq 10^{12}$. 2. $1 \ \mathrm{fr} \ \mathrm{id}$: time-space $i$ develops from time-space $\mathrm{fr}$, and humans abandon the planet with number $\mathrm{id}$. The testdata guarantees that this planet is colonized in time-space $\mathrm{fr}$. Also, $\mathrm{id} > 0$, meaning Earth will never be abandoned. In both cases above, all parameters are positive integers, and adjacent integers are separated by one space. It is also guaranteed that $0 \leq \mathrm{fr} < i$. No other cases will appear. The next $m$ lines each describe one time-space trip by Little R. Each line contains two positive integers $s$ and $x_0$, meaning that Little R travels to parallel time-space $s$, and the device fixes the $x$ coordinate to $x_0$. It is guaranteed that $0 \leq s < n$ and $|x_0| \leq 10^6$.

Output $m$ lines. The $i$-th line should be the minimum total cost to complete the investigation for the $i$-th trip.

For the first $5\%$ of the testdata, $n, m \leq 100$. There is another $35\%$ of the testdata with $n, m \leq 10^5$. Among them, for $15\%$ of the testdata, humans never abandon planets, and for another $10\%$ of the testdata, the $x$ value is the same for every trip. For the remaining testdata, $n, m \leq 5 \times 10^5$. Among them, for $10\%$ of the testdata, the $x$ value is the same for every trip, and for $35\%$ of the testdata, time-space $i$ develops from time-space $i - 1$. In this $35\%$, there is $15\%$ of the testdata where humans never abandon planets. Because the compressed file is too large to upload, for each subtask there is one and only one test point, corresponding to its score. Translated by ChatGPT 5