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, c_0$ ($1 \leq n, m \leq 5 \times 10^5, 0 \leq c_0 \leq 10^{12}$)，$n$ 表示平行时空数量，这些平行时空的编号为 $0$ 到 $n-1$ 的整数，初始时空的编号为 $0$。$m$ 表示小 R 进行的时空旅行的次数，$c_0$ 表示在地球进行调查的花费。
接下来 $n-1$ 行，依次描述平行时空 $1$ 到 $n-1$，其中第 $i$ 行分两种情况：
0 fr id x y z c：表示编号为 $i$ 的平行时空由编号为 $\mathrm{fr}$ 的时空发展而来，人类殖民了一个编号为 $\mathrm{id}$ 的星球，该星球的坐标为 $(x, y, z)$，在该星球进行调查的花费为 $c$。数据保证给出星球的编号不重复，且 $1 \leq \mathrm{id} < n$；保证 $|x|, |y|, |z| \leq 10^6, 0 \leq c \leq 10^{12}$。1 fr id：表示编号为 $i$ 的平行时空由编号为 $\mathrm{fr}$ 的时空发展而来，人类放弃了编号为 $\mathrm{id}$ 的星球。数据保证该星球在编号为 $\mathrm{fr}$ 的时空中处于被殖民的状态；保证 $\mathrm{id} \geq 1$，即地球一定不会被放弃。上述两种情况中，各参数均为正数，相邻整数之间均用一个空格隔开；均保证 $0 \leq \mathrm{fr} < i$。保证不会出现上述两种之外的情况。
接下来 $m$ 行，每行表示小 R 进行的一次时空旅行。每行包括 2 个正数 $s$ 和 $x_0$，表示小 R 到编号为 $s$ 的平行时空进行了一次时空旅行，时空旅行仪上的 $x$ 坐标被固定为了 $x_0$。
输出 $m$ 行，分别表示每次旅行完成调查的最小总花费。
看一点有点可持久化数据结构的即视感……
看两眼发现不太对劲，可持久化线段树？可持久化平衡树？维护什么东西？好像并不好维护的样子。
不过首先 $y$ 和 $z$ 就是个 (骗人的) 大废物，每次旅行的时候，只要将 $y, z$ 调整即可，因此每个星球的属性只有 $x$ 和 $c$，且去星球 $(x_i, c_i)$ 的花费就是 $(x - x_i)^2 + c$。
因此每个星球相当于一个 "二次函数"，每次询问一个点在所有二次函数中取值的最小值。
看三眼发现又不太对劲，这个二次函数的系数恒等于 $1$？哦不，项 $x_0^2$ 只和询问有关，和星球无关！也就是说，每个星球是一个一次函数！
因此我们可以用一条直线 $y = Ax + B$ 来表示星球 $(x_i, c_i)$，其中 $A = 2x_i, B = -x_i^2-c$ (约定以下 "直线" 就代表星球)。我们需要得到某个 $x_0$ 代入所有直线后取值的最大值，然后用 $x_0^2$ 相减记得最小值。
不过这个直线一会儿出现，一会儿消失还真有点麻烦，再说题目也没有强制在线，因此当然按照询问排序离线做啦！(听说这题强制在线不可做？)
那么这种时空的发展就形成一个树状结构，按照套路先研究链，然后根据 dfs 序、树链剖分、倍增等等处理树就轻而易举了。
链状结构，也就是说 $\mathrm{fr}_i = i-1$。那么一条直线存在 (即星球被殖民) 的时间一定是一个区间，且询问的时候就是询问该时刻所有直线代入的最大值？直线代入的最大值是什么？半平面交 (形成下凸包) 啊！(引入之前一道题的图)
那么对 $n$ 个时空分别求半平面交显然是不现实的 ($O(n^2)$ 的复杂度)，那么怎么办？由于是一个区间，因此考虑使用时间戳线段树！
将每条直线加入线段树，可知至多被加入线段树中 $O(\log n)$ 个节点，那么询问的时候只需要求线段树根节点到该叶节点的路径上所有直线的最大值即可。
因此询问也可以被加入线段树，不过要进行节点合并，因此，每个询问也被加入了 $O(\log n)$ 个节点。
最后就简单了，对线段树每个节点 (用单调栈) 求一遍半平面交，把该节点上的所有询问代入即得。
于是链上的故事就讲完了。接下来是树上的故事了。
由于一条直线的加入 (删除) 影响的是一棵子树 (且给出的编号不重复)，那么一条直线存在的时间就是一个大子树减去它里面的几个小子树！不说也明白，这肯定需要使用 dfs 序。
即，一条直线存在的时间在 dfs 序中是连续的若干段。不过这没关系，所有直线存在的时间的段数是 $O(n)$ 的，因此加入线段树还是 $O(n \log n)$。询问，完全类似地，复杂度为 $O(m \log n)$，于是总时间复杂度为 $O \left( (n+m) \log n \right)$。
#include <bits/stdc++.h>
#define N 512202
#define stack scx
#define INF 0xc0c0c0c0c0c0c0c0
using namespace std;
typedef long long ll;
struct star{
ll k, b; // line y = kx + b
int apr, dis; // appearances and disappearances
star (): k(0), b(0), apr(-1), dis(-1) {}
}s[N];
struct request{
int s, x, id; ll res;
request * read(int id0) {scanf("%d%d", &s, &x); id = id0; res = INF; return this;}
bool operator < (const request &B) const {return x < B.x;}
}qry[N];
int n, q;
int dis_next[N], ord[N], seg[N];
int p[N], fc[N], nc[N];
int cnt = 0, id[N], size[N];
star *stack[N]; ll inter[N], ans[N];
inline void up(ll &x, const ll y) {x < y ? x = y : 0;}
inline bool cmp(const int x, const int y) {return s[x].k < s[y].k || s[x].k == s[y].k && s[x].b < s[y].b;}
inline bool check(const star A, const star B, const star C) {return (B.b - A.b) * (B.k - C.k) <= (C.b - B.b) * (A.k - B.k);} // ensure A.k > B.k > C.k
namespace ST{
#define segc int M = L + R - 1 >> 1, lc = id << 1, rc = lc | 1
struct node{
vector <int> ln, req;
}x[N << 2];
void adds(int id, int L, int R, int ql, int qr, int v){
if(ql <= L && R <= qr) {x[id].ln.push_back(v); return;}
segc;
if(ql <= M) adds(lc, L, M, ql, min(qr, M), v);
if(qr > M) adds(rc, M + 1, R, max(ql, M + 1), qr, v);
}
void addq(int id, int L, int R, int h, int v){
if(L == R) {x[id].req.push_back(v); return;}
segc; h <= M ? addq(lc, L, M, h, v) : addq(rc, M + 1, R, h, v);
}
void combine(int id, int L, int R){
if(L == R) return;
segc; combine(lc, L, M); combine(rc, M + 1, R);
x[id].req.assign(x[lc].req.size() + x[rc].req.size(), 0);
merge(x[lc].req.begin(), x[lc].req.end(), x[rc].req.begin(), x[rc].req.end(), x[id].req.begin());
}
void solve(int id, int L, int R){
int n = x[id].ln.size(), m = x[id].req.size(), i = 0, j = 0, top = 0, y;
for(i = 0; i < n; ++i){
for(y = x[id].ln[i]; top && stack[top]->k == s[y].k; --top);
for(; top > 1 && check(s[y], *stack[top], *stack[top - 1]); --top);
stack[++top] = s + y;
}
if(top){
for(i = 1; i < top; ++i){
inter[i] = (stack[i]->b >= stack[i + 1]->b ?
(stack[i]->b - stack[i + 1]->b) / (stack[i + 1]->k - stack[i]->k) :
(stack[i]->b - stack[i + 1]->b + 1) / (stack[i + 1]->k - stack[i]->k) - 1
);
for(; j < m && qry[y = x[id].req[j]].x <= inter[i]; ++j)
up(qry[y].res, stack[i]->k * qry[y].x + stack[i]->b);
}
for(; j < m; ++j)
y = x[id].req[j], up(qry[y].res, stack[top]->k * qry[y].x + stack[top]->b);
}
segc;
if(L != R) {solve(lc, L, M); solve(rc, M + 1, R);}
}
}
inline void link(int x, int px) {nc[x] = fc[px]; fc[px] = x;}
void read(){
int i, x, op, Id; ll r;
memset(fc, -1, sizeof fc);
scanf("%d%d%lld", &n, &q, &r);
s[0].apr = 0; s[0].b = -r;
for(i = 1; i < n; ++i){
scanf("%d%d%d", &op, p + i, &Id);
if(op){
dis_next[i] = s[Id].dis; s[Id].dis = i;
}else{
scanf("%d%*d%*d%lld", &x, &r);
s[Id].apr = i;
s[Id].k = x << 1; s[Id].b = -(r + (ll)x * x);
// f(t) = (2x) t - (x^2+c) + Constant. (and get max)
}
link(i, p[i]);
}
}
void dfs(int x){
int y;
id[x] = ++cnt; size[x] = 1;
for(y = fc[x]; ~y; y = nc[y]){
dfs(y); size[x] += size[y];
}
}
void add_line(){
int z = 0, m, i, j, p;
dfs(0);
for(i = 0; i < n; ++i) if(~s[i].apr) ord[z++] = i;
sort(ord, ord + z, cmp);
for(i = 0; i < z; ++i){
p = s[j = ord[i]].apr; m = 0;
seg[m++] = id[p]; seg[m++] = id[p] + size[p];
for(p = s[j].dis; ~p; p = dis_next[p]){
seg[m++] = id[p]; seg[m++] = id[p] + size[p];
}
sort(seg, seg + m);
for(p = 0; p < m; p += 2)
if(seg[p] < seg[p + 1])
ST::adds(1, 1, n, seg[p], seg[p + 1] - 1, j);
}
}
void queries_solve(){
int i, s, x;
for(i = 0; i < q; ++i) qry[i].read(i);
sort(qry, qry + q);
for(i = 0; i < q; ++i) ST::addq(1, 1, n, id[qry[i].s], i);
ST::combine(1, 1, n);
ST::solve(1, 1, n);
for(i = 0; i < q; ++i) ans[qry[i].id] = (ll)qry[i].x * qry[i].x - qry[i].res;
for(i = 0; i < q; ++i) printf("%lld\n", ans[i]);
}
int main(){
read();
add_line();
queries_solve();
return 0;
}
坑1：不知道大家有没有发现，由于半平面交需要排序，因此时间复杂度可能退化到 $O(n \log^2 n)$。不过这可以解决，只需一开始将所有直线按照斜率排序，然后依次加入线段树，那么就避免了半平面交中排序的复杂度。类似地，询问也可以按照 $x_0$ 排序。
坑2：半平面交后，需要将所有询问代入，此时需要求下凸包中两两直线的交点，此时需要注意除法的取整方向 (即统一向下取整或统一向上取整)，而 C++ 的除法是向 0 取整的，这个需要注意。