首先题中的 \(y,z\) 好像没啥用……
首先对于每一次询问，要求 \(\min((x_0-x_i)^2+c_i)\)
设 \((x_0-x_i)^2+c_i=ans\)。
那么 \(x_0^2+x_i^2-2x_0x_i+c_i=ans\)
所以 \(x_0^2+x_i^2+c_i=2x_0x_i+ans\)。
这个式子明显为 \(y=kx+b\) 的形式，所以可以维护下凸包求解。
那么每个点的坐标即为 \((x_i,x_i^2+c_i)\)，每个询问的斜率为 \(2x_0\)，然后对于每个区间二分求解。
但是有时间变化，想到线段树分治。
首先所有的时间节点成一个树形结构，那么我们可以对这棵树遍历一遍，用 dfs 序对线段树编号。
对于一个点加入，那么会从这个节点开始，到遍历整棵子树完结束，那么对整棵子树加入一个节点。
如果删除一个点，从这个节点开始，到整棵子树完结束，不进行加操作，遍历完子树后，进行加操作。
就如同加上 \((l_1,r_1)\)，减去 \((l_2,r_2)\)，就等同于加上 \((l_1,l_2-1),(r_1+1,r_2)\) 两个区间。
先将每个点按 \(x\) 为第一关键字从小到大排序，\(y\) 为第二关键字从大到小排序，然后再求解。
时间复杂度：\(O(n\times \log_2^2(n))\)。
考虑优化。
将询问按照斜率从小到大排序，然后对于线段树每个节点间的斜率是有单调性的，记录上次询问得到的下标，然后下次询问就可以直接从这个地方开始。
几个细节：
1、不能全开 long long，会 MLE。
2、\(x\) 坐标相同时要处理一下。
3、注意询问中的时间与线段树中重新编号的区间不同。
时间复杂度：\(O(n\times\log(n))\)。
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N=5e5+5;
int n,m,tim=-1,nl,nr,dfn[N];
ll ans[N],k,res;
bool ss[N];
struct node
{
int name;
ll x,y;
}a[N];
struct segmentree
{
vector<int>t;
int cnt,to;
}f[4*N];
struct ask
{
int name,tim;
ll k;
}q[N];
bool cmp(node x,node y)
{
if(x.x==y.x)return x.x*x.x+x.y>y.x*y.x+y.y;
return x.x<y.x;
}
bool cmp2(ask x,ask y)
{
return x.k<y.k;
}
vector<pii>s[N];
vector<int>fr[N],to[N];
void dfs(int x,int name)
{
dfn[x]=++tim;
if(ss[x])fr[name].push_back(tim);
if(!ss[x])to[name].push_back(tim-1);
int len=s[x].size();
for(int i=0;i<len;i++)dfs(s[x][i].first,s[x][i].second);
if(ss[x])to[name].push_back(tim);
if(!ss[x])fr[name].push_back(tim+1);
}
double clac(int x,int y)
{
if(a[x].x==a[y].x)return -1e18;
return 1.0*(a[x].x*a[x].x+a[x].y-a[y].x*a[y].x-a[y].y)/1.0/(a[x].x-a[y].x);
}
ll clac9(ll x)
{
return x*x;
}
inline int ls(int x)
{
return x<<1;
}
inline int rs(int x)
{
return x<<1|1;
}
void build(int x,int l,int r)
{
f[x].cnt=-1;
f[x].to=0;
if(l==r)return;
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
}
void update(int x,int l,int r)
{
if(l>=nl&&r<=nr)
{
while(f[x].cnt>0&&clac(f[x].t[f[x].cnt],f[x].t[f[x].cnt-1])>=clac(f[x].t[f[x].cnt],k))f[x].cnt--;
int len=f[x].t.size();
if(len-1==f[x].cnt)f[x].t.push_back(k),f[x].cnt++;
else f[x].t[++f[x].cnt]=k;
return;
}
int mid=(l+r)>>1;
if(mid>=nl)update(ls(x),l,mid);
if(mid<nr)update(rs(x),mid+1,r);
}
void search(int x,int l,int r)
{
for(;f[x].to<f[x].cnt;f[x].to++)
if(clac(f[x].t[f[x].to],f[x].t[f[x].to+1])>=k)break;
if(f[x].cnt!=-1)res=min(res,clac9(k/2-a[f[x].t[f[x].to]].x)+a[f[x].t[f[x].to]].y);
if(l==r)return;
int mid=(l+r)>>1;
if(mid>=nl)search(ls(x),l,mid);
else search(rs(x),mid+1,r);
}
signed main()
{
scanf("%d%d%lld",&n,&m,&a[0].y);
for(int i=0;i<n;i++)a[i].name=-1;
a[0].name=0;
a[0].x=0;
ss[0]=1;
for(int i=1;i<=n-1;i++)
{
int opt;
scanf("%d",&opt);
if(opt==0)
{
int ul1,ul2,fa,name;
scanf("%d%d",&fa,&name);
scanf("%lld%d%d%lld",&a[name].x,&ul1,&ul2,&a[name].y);
a[name].name=name;
s[fa].push_back({i,name});
ss[i]=1;
}
else
{
int fa,name;
scanf("%d%d",&fa,&name);
s[fa].push_back({i,name});
}
}
dfs(0,0);
sort(a,a+n,cmp);
build(1,0,n-1);
for(int i=0;i<n;i++)
{
int x=a[i].name;
if(x==-1)continue;
int len=fr[x].size();
for(int j=0;j<len;j++)
{
nl=fr[x][j],nr=to[x][j],k=i;
if(nr<nl)continue;
update(1,0,n-1);
}
}
for(int i=1;i<=m;i++)
{
scanf("%d%lld",&q[i].tim,&q[i].k);
q[i].name=i;
}
sort(q+1,q+1+m,cmp2);
for(int i=1;i<=m;i++)
{
nl=dfn[q[i].tim],k=2*q[i].k;
res=1e18;
search(1,0,n-1);
ans[q[i].name]=res;
}
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}