RT，AC 了测试点 1,2,6,7。

悬赏 1 关注。

代码中世界编号和星球编号均从 $1$ 开始。

为了卡空间线段树只开了 3 倍空间，自测没事。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P__ puts("")
#define PU puts("--------------------")
#define popc __builtin_popcount
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
#define reprange(a,b,c,d) for(int a=b;a<=c;a+=d)
#define perrange(a,b,c,d) for(int a=b;a>=c;a-=d)
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
#define int long long 
//#define int __int128
using namespace std;
bool greating(int x,int y){return x>y;}
bool greatingll(long long x,long long y){return x>y;}
bool smallingll(long long x,long long y){return x<y;}
namespace Fread {
	const int SIZE=1<<21;
	char buf[SIZE],*S,*T;
	inline char getc(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return '\n';}return *S++;}
}
namespace Fwrite{
	const int SIZE=1<<21;
	char buf[SIZE],*S=buf,*T=buf+SIZE;
	inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}
	inline void putc(char c){*S++=c;if(S==T)flush();}
	struct NTR{~NTR(){flush();}}ztr;
}
/*#ifdef ONLINE_JUDGE
#define getchar Fread::getc
#define putchar Fwrite::putc
#endif*/
inline int rd(){
	int x=0,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-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
	if(x<0){x=-x;putchar('-');}
	int y=0;char z[40];
	while(x||!y){z[y++]=x%10+48;x/=10;}
	while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=5e5+1,maxm=4e5+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,m,Q;
int fa[maxn];
int a[maxn],c[maxn];
int op[maxn],id[maxn];
int lst[maxn],lstlst[maxn];
int dfn[maxn],dfncnt;
int siz[maxn];
vector<int>G[maxn];
void dfs(int x){
	siz[x]=1,dfn[x]=++dfncnt;
	for(int u:G[x])dfs(u),siz[x]+=siz[u];
}
pii operator-(pii x,pii y){
	return mp(x.fi-y.fi,x.se-y.se);
}
int cross(pii x,pii y){
	return x.fi*y.se-x.se*y.fi;
}
int calc(pii x,int y){
	return x.se-2*y*x.fi+y*y;
}
namespace segtree{
	struct node{
		vector<pii>q;
		int hd=0;
	}d[maxn*3];
	void upd(int ll,int rr,pii x,int l=1,int r=n,int p=1){
		if(ll>rr)return;
		if(ll<=l&&r<=rr){
//			printf("Pair (%lld,%lld) inserts in %d.\n",x.fi,x.se,p);
			#define tl (int)q.size()-1
			#define q d[p].q
//			write(tl,32);
			while(tl>0&&cross(x-q[tl],q[tl]-q[tl-1])>=0)q.pop_back();
			q.pb(x);
			#undef tl
			#undef q
			return;
		}
		int mid=l+r>>1;
		if(ll<=mid)upd(ll,rr,x,l,mid,lson(p));
		if(rr>mid)upd(ll,rr,x,mid+1,r,rson(p));
	}
	int qry(int t,int x,int l=1,int r=n,int p=1){
		int res=llinf;
		#define hd d[p].hd
		#define tl (int)q.size()-1
		#define q d[p].q
//		write(tl,32);
		if(!q.empty()){
//			while(hd<tl&&cross(pii(x,1),q[hd+1]-q[hd])<=0)hd++;
			while(hd<tl&&calc(q[hd],x)>=calc(q[hd+1],x))hd++;
			res=calc(q[hd],x);
		}
		#undef hd
		#undef tl
		#undef q
		if(l==r)return res;
		int mid=l+r>>1;
		if(t<=mid)return min(res,qry(t,x,l,mid,lson(p)));
		else return min(res,qry(t,x,mid+1,r,rson(p)));
	}
}using namespace segtree;
int cnt;
struct Planet{
	int l,r;pii x;
	bool operator<(const Planet &p)const{
		return x<p.x;
	}
}e[maxn<<1];
struct Query{
	int x,y,ans;
	int id;
	bool operator<(const Query &p)const{
		return y<p.y;
	}
}q[maxn];
bool cmp(Query p,Query pp){
	return p.id<pp.id;
}
void solve_the_problem(){
	n=rd(),Q=rd(),c[1]=rd();
	rep(i,2,n){
		int z,y;
		op[i]=rd(),fa[i]=rd()+1,id[i]=rd()+1;
		if(!op[i])a[id[i]]=rd(),y=rd(),z=rd(),c[id[i]]=rd();
		G[fa[i]].pb(i);
	}
	dfs(1);
//	rep(i,1,n)write(siz[i],32);P__; 
	rep(i,2,n){
		if(!op[i]){
			lst[id[i]]=dfn[i],lstlst[id[i]]=dfn[i]+siz[i]-1;
		}else{
			e[++cnt]=(Planet){lst[id[i]],dfn[i]-1,mp(a[id[i]],a[id[i]]*a[id[i]]+c[id[i]])};
			lst[id[i]]=dfn[i]+siz[i];
		}
	}
	e[++cnt]=(Planet){1,n,mp(0,c[1])};
	rep(i,1,n)if(lst[i])e[++cnt]=(Planet){lst[i],lstlst[i],mp(a[i],a[i]*a[i]+c[i])};
	sort(e+1,e+cnt+1);
	rep(i,1,cnt){
		upd(e[i].l,e[i].r,e[i].x);
//		write(e[i].l,32),write(e[i].r,32),write(e[i].x.fi,32),write(e[i].x.se,10);
	}
	rep(i,1,Q)q[i].x=rd()+1,q[i].y=rd(),q[i].id=i;
	sort(q+1,q+Q+1);
	rep(i,1,Q){
//		write(q[i].x,32),write(q[i].id,10);
		q[i].ans=qry(dfn[q[i].x],q[i].y);
	}
	sort(q+1,q+Q+1,cmp);
	rep(i,1,Q)write(q[i].ans,10);
}
bool Med;
signed main(){
//	freopen(".in","r",stdin);freopen(".out","w",stdout);
//	fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
	int _=1;while(_--)solve_the_problem();
}
/*

*/