【题解】
首先y、z是没有用的。。
然后式子就是w = (x0-xi)^2+ci的最小值，化出来可以变成一个直线的形式。
然后我们可以用线段树维护dfs序上的每个点。
每个点维护经过这个点的所有直线（标记永久化），也就是维护上凸壳。
然后我们把询问按照x排序，每次决策点只会后移。所以复杂度就有保证啦！
真**难写
还有一个十分有趣的事实啊
我用一个号交完ac在另一个号再交就RE了啊。。。
不管了反正过了
# include <vector> # include <stdio.h> # include <string.h> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, q, s[M], ps[M]; ll c0, ans[M]; vector<int> b[M]; struct planet { int x; ll c; planet() {} planet(int x, ll c) : x(x), c(c) {} friend bool operator < (planet a, planet b) { return a.x<b.x; } }p[M]; struct line { ll k, b; line() {} line(ll k, ll b) : k(k), b(b) {} inline ll set(int x) { return k*(ll)x+b; } }; struct quest { int s, x0, id; quest() {} quest(int s, int x0, int id) : s(s), x0(x0), id(id) {} friend bool operator < (quest a, quest b) { return a.x0<b.x0; } }qu[M]; int head[M], nxt[M], to[M], tot, in[M], out[M], DFN; inline void add(int u, int v) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; } inline void dfs(int x) { in[x] = ++DFN; for (int i=head[x]; i; i=nxt[i]) dfs(to[i]); out[x] = DFN; } inline bool cmp(int x, int y) { return p[x].x<p[y].x; } inline bool cmp_b(int x, int y) { return in[x] < in[y]; } namespace SMT { const int M = 2e6 + 10; vector<line> w[M]; int lst[M]; inline bool canout(line a, line b, line c) { if(b.k == c.k) return b.b >= c.b; return 1.0*(b.b-a.b)*(a.k-c.k) > 1.0*(c.b-a.b) * (a.k-b.k); } inline void change(int x, int l, int r, int L, int R, line add) { if(L <= l && r <= R) { if(w[x].size()) { while(w[x].size() > 1 && canout(w[x][w[x].size()-2], w[x][w[x].size()-1], add)) w[x].pop_back(); w[x].push_back(add); } else w[x].push_back(add); return ; } int mid = l+r>>1; if(L <= mid) change(x<<1, l, mid, L, R, add); if(R > mid) change(x<<1|1, mid+1, r, L, R, add); } inline ll query(int x, int l, int r, int pos, int x0) { while(lst[x]+1 < w[x].size() && w[x][lst[x]].set(x0) > w[x][lst[x]+1].set(x0)) ++lst[x]; ll cur = (w[x].size() ? w[x][lst[x]].set(x0) : 1e18); if(l == r) return cur; int mid = l+r>>1; if(pos <= mid) return min(cur, query(x<<1, l, mid, pos, x0)); else return min(cur, query(x<<1|1, mid+1, r, pos, x0)); } inline void change(int L, int R, line add) { if(L>R) return; change(1, 1, DFN, L, R, add); } inline ll query(int pos, int x0) { return query(1, 1, DFN, pos, x0); } } int main() { scanf("%d%d%lld", &n, &q, &c0); for (int i=1, op, fr, id, x, c; i<n; ++i) { ps[i] = i; scanf("%d%d%d", &op, &fr, &id); if(op == 0) { scanf("%d%*d%*d%lld", &x, &c); s[id] = i; p[id] = planet(x, c); } else b[id].push_back(i); add(fr, i); } dfs(0); sort(ps+1, ps+n, cmp); for (int i=1, t; i<n; ++i) { if(s[ps[i]]) { int id = ps[i], se = s[id]; line L = line(-2ll*p[id].x, 1ll*p[id].x*p[id].x+p[id].c); if(b[id].size()) { sort(b[id].begin(), b[id].end(), cmp_b); t = b[id].size(); SMT::change(in[se], in[b[id][0]]-1, L); SMT::change(out[b[id][t-1]]+1, out[se], L); for (int j=1; j<t; ++j) SMT::change(out[b[id][j-1]]+1, in[b[id][j]]-1, L); } else SMT::change(in[se], out[se], L); } } for (int i=1; i<=q; ++i) { scanf("%d%d", &qu[i].s, &qu[i].x0); qu[i].id=i; } sort(qu+1, qu+q+1); for (int i=1; i<=q; ++i) ans[qu[i].id] = 1ll * qu[i].x0 * qu[i].x0 + min(c0, SMT::query(in[qu[i].s], qu[i].x0)); for (int i=1; i<=q; ++i) printf("%lld ", ans[i]); return 0; }