前置知识：线段树分治。
题意
给定 \(n\) 个节点的树，每个节点有一个二元组集合 \(S_i\)。
这个集合有一个限制：\(S_i\) 一定是 \(S_{fa_i}\) 中删除一个二元组或者加一个二元组，并且加进来的二元组互不相同。
现在有 \(m\) 个询问，每个询问给出 \(k, h\) 表示查询 \(\min\limits_{(x, c) \in S_k}\{(x - h)^2 + c\}\)。
题解
好题啊，首先可以将式子拆成好算的形式：
\[\begin{aligned} &(x - h)^2 + cc\\ =&x^2 + h^2 - 2xh + c\\ =&h^2 + [-2xh + (x^2 + c)] \end{aligned} \]这相当于求 \(S_k\) 中所有斜率为 \(-2x\)，截距为 \(x^2 + c\) 的直线在 \(x = h\) 时纵坐标的最大值。而这是李超线段树的经典应用。于是考虑先把询问离线下来，接着 dfs 整棵树并更新这个 \(S\)，再对于这个节点的每个询问一一回答即可。
可是李超线段树是不支持删除的，只支持撤销（实际上大部分数据结构都支持撤销）。于是考虑把删除转化为撤销，故使用线段树分治。所以新的问题又出现了，如何找一个直线在哪些节点上出现了。观察一下可以发现，对于所有包含同一条直线的点，这些点在树上一定是一个连通块，因为题目中保证了二元组互不相同。
所以如果将树的 dfn 序处理出来，包含一条直线的所有点的 dfn 序集合，一定是由若干区间组成的，因为每有一个删除操作，都相当于是在这条直线的区间中挖掉一部分。假设区间数量为 \(t\)，易证 \(\sum t\) 是 \(O(n)\) 的。这样就可以使用线段树分治了，时间复杂度 \(O(n \log^2 n)\)。
代码
code:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 5E5 + 5;
int n, m, q;
vector <int> G[N];
struct line {
i64 k, b;
void gen(int x, int c) {
k = -2LL * x;
b = 1LL * x * x + c;
}
} li[N];
struct opr {int opt, id;} a[N];
int dl[N], dr[N], tot; vector <pair <int, int>> ed[N];
pair <int, int> be[N];
void dfs(int x, int fa) {
dl[x] = ++tot;
for (auto v : G[x]) {
if (v == fa) continue;
dfs(v, x);
} dr[x] = tot;
if (a[x].opt == 1) ed[a[x].id].emplace_back(dl[x], dr[x]);
else be[a[x].id] = make_pair(dl[x], dr[x]);
}
i64 Ans[N];
vector <int> v[N << 2];
vector <pair <int, int>> qs[N];
stack <pair <int, int>> st;
struct lc_segt {
int root, tot;
struct node {int ls, rs, s;} t[N << 5];
i64 calc(int u, int v) {return li[u].k * v + li[u].b;}
void upd(int &x, int l, int r, int u) {
if (!x) x = ++tot;
if (t[x].s == 0) {
st.emplace(x, 0);
t[x].s = u;
return ;
} int mid = (l + r) >> 1, &v = t[x].s;
if (calc(u, mid) < calc(v, mid)) {
st.emplace(x, v);
swap(u, v);
}
if (l == r) return ;
if (calc(u, l) < calc(v, l)) upd(t[x].ls, l, mid, u);
if (calc(u, r) < calc(v, r)) upd(t[x].rs, mid + 1, r, u);
}
i64 query(int x, int l, int r, int p) {
if (!x || !t[x].s) return 2E18;
i64 now = calc(t[x].s, p); int mid = (l + r) >> 1;
if (l == r) return now;
if (p <= mid) return min(now, query(t[x].ls, l, mid, p));
else return min(now, query(t[x].rs, mid + 1, r, p));
}
void push(int id) {upd(root, -1E6, 1E6, id);}
i64 query(int p) {return query(root, -1E6, 1E6, p);}
void cl(int to) {
while ((int)st.size() > to) {
auto [x, y] = st.top(); st.pop();
t[x].s = y;
}
}
} t;
void ins(int x, int l, int r, int L, int R, int id) {
if (L > R) return ;
if (l >= L && r <= R) {
v[x].emplace_back(id);
return ;
} int mid = (l + r) >> 1;
if (L <= mid) ins(x << 1, l, mid, L, R, id);
if (R > mid) ins(x << 1 | 1, mid + 1, r, L, R, id);
}
void solve(int x, int l, int r) {
int now = st.size();
for (auto id : v[x]) t.push(id);
int mid = (l + r) >> 1;
if (l == r) {
for (auto [p, id] : qs[l]) {
i64 tmp = t.query(p);
Ans[id] = tmp + 1LL * p * p;
}
} else solve(x << 1, l, mid), solve(x << 1 | 1, mid + 1, r);
t.cl(now);
}
signed main(void) {
ios :: sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int c0;
cin >> n >> q >> c0; li[1].gen(0, c0); a[1].opt = 0; a[1].id = 1;
for (int i = 2; i <= n; ++i) {
int opt, fr, id; cin >> opt >> fr >> id;
++fr, ++id; G[fr].emplace_back(i);
if (opt == 0) {int x, c; cin >> x >> c >> c >> c; li[id].gen(x, c);}
a[i].opt = opt; a[i].id = id;
} dfs(1, 0);
for (int i = 1; i <= n; ++i) if (be[i].first) {
sort(ed[i].begin(), ed[i].end());
int nl = be[i].first;
for (auto [l, r] : ed[i]) {
ins(1, 1, n, nl, l - 1, i);
nl = r + 1;
} ins(1, 1, n, nl, be[i].second, i);
}
for (int i = 1; i <= q; ++i) {
int s, x; cin >> s >> x; ++s;
qs[dl[s]].emplace_back(x, i);
} solve(1, 1, n);
for (int i = 1; i <= q; ++i) cout << Ans[i] << '\n';
}