记录编号	593767	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CTSC 2016]时空旅行	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	20.281 s
提交时间	2024-09-12 20:11:03	内存使用	145.42 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 5e5+10;
const ll inf = 1e18;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}
void cmin(ll &x,ll y){x = min(x,y);}


int n,m,c;

ll d[N],z[N],ans[N],len;
struct tubao{
	vector<int>st;
	int l = 0,r = -1;
	ll X(int x){return d[x];}
	ll Y(int x){return d[x] * d[x] + z[x];}
	ll X(int x,int y){return X(x) - X(y);}
	ll Y(int x,int y){return Y(x) - Y(y);}
	void add(int x){
		while(l < r && X(x,st[r]) * Y(st[r],st[r-1]) >= X(st[r],st[r-1]) * Y(x,st[r]))r--;
		st.pb(x),st[++r] = x;
	}
	int ask(ll k){
		while(l < r && Y(st[l+1],st[l]) <= 2ll * k * X(st[l+1],st[l]))l++;
		return l <= r ? st[l] : -1;
	}
};


vector<int>e[N];
void add(int x,int y){e[x].pb(y);}
int dfn[N],siz[N],cnt;
void dfs(int x){
	dfn[x] = ++cnt,siz[x] = 1;
	for(int y : e[x])dfs(y),siz[x] += siz[y];
}


vector<int>g[N];
struct node{int id,pos,x,z;}a[N];
bool cmp(node a,node b){return a.x == b.x ? a.id < b.id : a.x < b.x;}
struct query{int s,x,id;}q[N];
bool cmp1(query a,query b){return a.x < b.x;}

struct segment{
	tubao s[N<<2];
	void insert(int p,int l,int r,int L,int R,int x){
		if(L <= l && r <= R)return s[p].add(x),void();
		int mid = l + r >> 1;
		if(L <= mid)insert(p<<1,l,mid,L,R,x);
		if(R > mid)insert(p<<1|1,mid+1,r,L,R,x);
	}
	void ask(int p,int l,int r,query x){
		int now = s[p].ask(x.x);
		if(now != -1)cmin(ans[x.id],(ll)(x.x - d[now]) * (x.x - d[now]) + z[now]);
		if(l == r)return;
		int mid = l + r >> 1;
		if(x.s <= mid)ask(p<<1,l,mid,x);
		else ask(p<<1|1,mid+1,r,x);
	}
}t;

void modify(node x){
	d[++len] = x.x,z[len] = x.z;
	int l = dfn[x.id];
	sort(g[x.pos].begin(),g[x.pos].end(),[&](int x,int y){return dfn[x] < dfn[y];});
	for(int y : g[x.pos])t.insert(1,1,n,l,dfn[y]-1,len),l = dfn[y] + siz[y];
	if(l <= dfn[x.id] + siz[x.id] - 1)t.insert(1,1,n,l,dfn[x.id] + siz[x.id] - 1,len);
}


int main(){
	freopen("CTSC2016travel.in","r",stdin);
	freopen("CTSC2016travel.out","w",stdout);
	n = read(),m = read(),c = read();
	a[1] = {1,0,0,c};
	for(int i = 2;i <= n;i++){
		int op = read(),las = read() + 1,id = read();
		add(las,i);
		if(op)g[id].pb(i);
		else{
			int x = read(),y = read(),z = read(),val = read();
			a[i] = {i,id,x,val};
		}
	}
	dfs(1);
	sort(a+1,a+1+n,cmp);
	for(int i = 1;i <= n;i++){
		if(!a[i].id)continue;
		modify(a[i]);
	}
	for(int i = 1;i <= m;i++)q[i] = {dfn[read()+1],(int)read(),i},ans[i] = inf;
	sort(q+1,q+1+m,cmp1);
	for(int i = 1;i <= m;i++)
		t.ask(1,1,n,q[i]);
	for(int i = 1;i <= m;i++)printf("%lld\n",ans[i]);

	return 0;

}