已经调 3h+ 了/ll

样例是 LibreOJ 的大样例。思路是线段树分治，每个节点维护凸包。

#include <bits/stdc++.h>
using namespace std;

using LL = __int128;
using ll = long long;
using ldb = long double;
using vi = vector < int >;
using pii = pair < int, int >;
using ull = unsigned long long;
#define pb push_back
#define ls(u) (u << 1)
#define rs(u) (u << 1 | 1)
#define ve vector < edge >
#define lowbit(x) ((x) & -(x))
#define sz(x) (int((x).size()))
#define all(a) (a).begin(), (a).end()
#define me(a, b) memset(a, b, sizeof(a))
#define L(i, j, k) for (int i = j; i <= int(k); i++)
#define R(i, j, k) for (int i = j; i >= int(k); i--)
#define qio() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
namespace io {
#define CF
#ifdef FILE
	char buf[1 << 21], *p1 = buf, *p2 = buf;
	#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
#else
	#ifndef CF
		#define getchar() getchar_unlocked()
	#endif
#endif
	int read() {
		int x = 0, f = 1; char ch = getchar();
		while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
		while (ch >= '0' && ch <= '9') {
			assert(10ll * x + (ch ^ '0') <= INT_MAX);
			x = x * 10 + (ch ^ '0'), ch = getchar();
		} return x * f;
	}
	template < class T = int > void read(T& x) {
		x = 0; int f = 1; char ch(getchar());
		while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
		while (ch >= '0' && ch <= '9') { x = x * 10 + (ch ^ '0'), ch = getchar(); } x *= f;
	}
} using io::read;

template < class T > ostream& operator << (ostream& out, vector < T > v) {
	out << '[';  if (!v.empty()) { L(i, 0, v.size() - 2) out << v[i] << ','; out << v[v.size() - 1]; } return out << ']';
}
// #define DEBUG
namespace Dbg {
	template < class T > void dbg(char *f, T t) { cerr << f << '=' << t << endl; }
	template < class T, class ...Ar > void dbg(char *f, T x, Ar... y) {
		while (*f != ',') { cerr << *f++; } cerr << '=' << x << ','; dbg(f + 1, y...);
	}
}
#ifdef DEBUG
	#define gdb(...) cerr << "gdb in line " << __LINE__ << ": ", Dbg::dbg((char*)#__VA_ARGS__,__VA_ARGS__)
	#define debug cerr << "debug: " << __LINE__ << '\n'
#else
	#define gdb(...) void()
	#define debug void()
#endif

/* ================================= */

const int N = 5e5 + 5; // Adjust
const int V = 1e8 + 5;
const int notExist = -2e6 - 1;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;

#define F first
#define S second

struct Planet {
	ll k, b;
	vector < pii > influence;

	void split(pii del) {
		auto ori = influence.back();
		influence.pop_back();
		influence.pb({ori.F, del.F - 1});
		influence.pb({del.S + 1, ori.S});
	}
} planet[N];
struct Input {
	int opt, id;
} input[N];
struct Query {
	int u, x0, id;
	void input(int i) {
		u = read(), x0 = read(), id = i;
	}
} query[N];

struct point {
	ll x, y;
};
struct segment_tree {
	struct Convex {
		vector < point > pset;
		int head;

		Convex() {
			head = 0;
		}
		int size() {
			return sz(pset) - head;
		}
		bool pop_back(point a, point b, point c) {
			return 1ll * (b.y - a.y) * (c.x - b.x) > 1ll * (b.x - a.x) * (c.y - b.y);
		}
		bool useless(point a, point b, ll slope) {
			return b.y - a.y < slope * (b.x - a.x);
		}

		void add_back(point add) {
			while (size() > 1 && pop_back(pset[sz(pset) - 2], pset.back(), add))
				pset.pop_back();
			pset.pb(add);
		}
		ll query(ll x0) {
			while (size() > 1 && useless(pset[head], pset[head + 1], x0 * 2))
				++head, gdb(size());
			if (size() == 0)
				return INF;
			auto [x, y] = pset[head];
			gdb(x, y);
			return -2 * x0 * x + y + x0 * x0;
		}
	} convex[N << 2];

#define ls(u) (u << 1)
#define rs(u) (u << 1 | 1)

	void modify(int s, int t, int ql, int qr, int u, point add) {
		if (ql <= s && t <= qr) {
			convex[u].add_back(add);
			return;
		}
		int mid = (s + t) >> 1;
		if (mid >= ql)
			modify(s, mid, ql, qr, ls(u), add);
		if (mid < qr) 
			modify(mid + 1, t, ql, qr, rs(u), add);
	}
	ll query(int s, int t, int k, int u, ll x0) {
		ll res = convex[u].query(x0);
		gdb(s, t, k, u, x0, res);
		if (s == t) {
			return res;
		}
		int mid = (s + t) >> 1;
		if (mid >= k)
			return min(res, query(s, mid, k, ls(u), x0));
		else
			return min(res, query(mid + 1, t, k, rs(u), x0));
	}
} sgt;

int n, m, dfn_l[N], dfn_r[N];
bool exist[N];
vi G[N];

int get_dfs_order(int u) {
	static int dfc = 0;
	dfn_l[u] = dfn_r[u] = ++dfc;
	
	for (int v : G[u])
		dfn_r[u] = max(dfn_r[u], get_dfs_order(v));

	return dfn_r[u];
}
void get_influence_range(int u) {
	if (input[u].opt == 0) {
		planet[input[u].id].influence.pb({dfn_l[u], dfn_r[u]});
	} else {
		planet[input[u].id].split({dfn_l[u], dfn_r[u]});
	}
	
	for (int v : G[u])
		get_influence_range(v);
}

int main() {
	n = read(), m = read(), read < ll >(planet[0].b);
	L(i, 1, n - 1) { 
		int opt = read(), fa = read(), id = read();
		G[fa].pb(i);
		if (opt == 0) {
			int x = read(); read(), read();
			ll c; read < ll >(c);
			planet[id] = {x, 1ll * x * x + c};
		}
		input[i] = {opt, id};
		exist[id] = 1;
	}
	L(i, 0, m - 1) {
		query[i].input(i);
	}

	L(i, 1, n - 1)
		if (!exist[i])
			planet[i].k = notExist;

	get_dfs_order(0), get_influence_range(0);
	sort(query, query + m, [](Query a, Query b) {
		return a.x0 < b.x0;
	});
	sort(planet, planet + n, [](Planet a, Planet b) {
		return a.k != b.k ? a.k < b.k : a.b < b.b;
	});

	L(i, 1, n - 1)
		if (planet[i].k == planet[i - 1].k)
			planet[i].k = notExist;
	
	L(i, 0, n - 1)
		if (planet[i].k != notExist) {
			for (pii add : planet[i].influence)
				if (add.F <= add.S) 
					sgt.modify(1, n, add.F, add.S, 1, {planet[i].k, planet[i].b});
		}

	vector < ll > ans(m);
	L(i, 0, m - 1) {
//		cerr << "calcing " << query[i].id << '\n';
		ans[query[i].id] = sgt.query(1, n, dfn_l[query[i].u], 1, query[i].x0);
	}

	for (ll i : ans)
		printf("%lld\n", i);

	return 0;
}