题目
Description
2045年，人类的技术突飞猛进，已经找到了进行时空旅行的方法。小R得到了一台时空旅行仪，他想用它调查不同 时空中人类的发展状况。
根据平行时空理论，宇宙中存在着很多独立的时空，每个时空在下一个时间点还会分化出若干个不同的时空。宇宙是一个三维空间，人类使用空间直角坐标系来描述空间中的一个位置，三维坐标分别是 x,y,z。
我们假设在初始的时空（编号为 0）中，人类存在于地球上（地球的坐标为 (0,0,0)），其它的时空都是从一个现有的时空发展而来。一个时空发生一个事件之后会发展成为另外一个时空（原来的时空不发生任何变化）。会影响小R的事件包括两类：
人类殖民了一个新的星球，该星球的状态变成”已被殖民”；
人类放弃了一个已被殖民的星球，该星球的状态变成”未被殖民”。每次进行时空旅行时，小R会先选定一个时空。在这个时空中，人类已经殖民了一些星球。
小R只要到达该时空中任意一个已被殖民的星球，就能调查人类的发展状况。
小R的时空旅行仪出现了一些问题，调整 x 坐标的按钮坏掉了，因此到达点的 x 坐标被固定了（每次旅行的 x 坐标值可能不同）。与此同时，他仍能任意调整到达点的 y 坐标和 z 坐标。
这个问题大大增大了小R的花费：因为时空旅行没有花费，但在太空中航行却需要花钱；同时，在不同的星球进行调查也可能会产生不同的费用。
假设小R将时空旅行的终点设为 A，他要进行调查的星球为 B：如果 A 与 B 的欧几里德距离为 d，那么他太空航行的花费就为 d^2；又如果星球 B 上进行调查的费用为 c，那么小R此次调查的总花费就为 d^2+c。
现在给定小R每次旅行到达的时空以及时空旅行仪上固定的 x 坐标值，请你计算出小R每次旅行完成调查的最小总花费。
Input
输入的第一行包含三个非负整数 n,m,c_0，n 表示平行时空数量，这些平行时空的编号为 0 到 n-1 的整数，初始时空的编号为 0。m 表示小R进行的时空旅行的次数，c_0 表示在地球进行调查的花费。保证 n,m 是正整数，0≤c_0≤10^12。
接下来 n-1 行，依次描述平行时空 1 到 n-1，其中第 i 行分两种情况：
0 fr id x y z c：表示编号为 i 的平行时空由编号为 fr 的时空发展而来，数据保证人类殖民了一个编号为 id 的星球，该星球的坐标为 (x,y,z)，在该星球进行调查的花费为 c。数据保证给出的星球编号不重复，且 0<id<n；保证 $\mid$x$\mid$,$\mid$y$\mid$,$\mid$z$\mid$≤10^6，0≤c≤10^12。
1 fr id：表示编号为 i 的平行时空由编号为 fr 的时空发展而来，人类放弃了编号为 id 的星球。数据保证该星球在编号为 fr 的时空中处于被殖民的状态；保证 id>0，即地球一定不会被放弃。
上述两种情况中，各参数均为整数，相邻整数之间均用一个空格隔开；均保证 0≤fr<i。保证不会出现上述两种之外的情况。
接下来 m 行，每行表示小R进行的一次时空旅行。每行包括 2 个整数 s 和 x_0，表示小R到编号为 s 的平行时空进行了一次时空旅行，时空旅行仪上的 x 坐标被固定为了 x_0。保证 0≤s<n，$\mid$ x_0 $\mid$ ≤10^6。N,M<=5*10^5
Output
输出 m 行，分别表示每次旅行完成调查的最小总花费。
Sample Input
4 4 2
0 0 1 8 2 3 7
0 1 2 10 1 6 2
1 1 1
1 4
2 8
2 6
3 8
Sample Output
18
6
11
66
题解
昊哥强推的题
然后ta自己都没做
题面很长……
读完之后发现$y,z$一点用都没有
因为星球存在时空是个区间，所以考虑把区间从树上薅下来然后线段树分治搞
根据题目，可以发现要求的就是$min((x_i-x)^2+c_i)$
拆开来看，就是$x_i^2-2x_ix+x^2+c_i$
先不管$x^2$，发现这个玩意就是斜率为$-2x_i$的一次函数
然后可以每个线段树节点维护一个凸包，按$x$大小离线询问再依次查询
因为vector维护单调栈栈底标号定成$1$了调了一下午……
原来以为要树链剖分薅区间改了好长时间……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<vector>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=5e5+5;
struct p{
int x,y;
}c[MAX];
struct q{
int fl,id;
}qwq[MAX];
struct u{
double x,y;
}qaq[MAX];
struct o{
int x,y,id;
bool operator< (const o &a)
const{
return qaq[id].x<qaq[a.id].x;
}
}qu[MAX];
struct v{
int x,id;
double y;
bool operator< (const v &a)
const{
return y<a.y;
}
}Qu[MAX];
int n,m,num,cnt,tot;
LL C0;
int h[MAX],fa[MAX],id[MAX],siz[MAX],qvq[MAX<<2];
LL ans[MAX];
vector<int> s[MAX<<2],L[MAX],R[MAX];
LL read()
{
LL x=0,fl=1;
char ch=getchar();
for(;!isdigit(ch);fl=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*fl;
}
void dfs(int x=1)
{
siz[x]=1,id[x]=++tot;
if(x!=1)
{
if(!qwq[x].fl) L[qwq[x].id].push_back(tot);
else R[qwq[x].id].push_back(tot-1);
}
for(int i=h[x];i;i=c[i].x)
dfs(c[i].y),siz[x]+=siz[c[i].y];
if(x!=1)
{
if(!qwq[x].fl) R[qwq[x].id].push_back(id[x]+siz[x]-1);
else L[qwq[x].id].push_back(id[x]+siz[x]);
}
}
double GET_K(u a,u b)
{
if(a.x==b.x)
{
if(a.y<b.y) return 1e18;
return -1e18;
}
return (b.y-a.y)/(b.x-a.x);
}
void change(int l,int r,int k,int L,int R,int id)
{
if(l==L&&r==R)
{
int Top=s[k].size()-1;
while(Top>0&&GET_K(qaq[s[k][Top-1]],qaq[s[k][Top]])>GET_K(qaq[s[k][Top]],qaq[id])) --Top,s[k].pop_back();
return void(s[k].push_back(id));
}
if(R<=mid) change(l,mid,tl,L,R,id);
else if(L>mid) change(mid+1,r,tr,L,R,id);
else change(l,mid,tl,L,mid,id),change(mid+1,r,tr,mid+1,R,id);
}
LL ask(int l,int r,int k,int x,double id)
{
int Top=s[k].size()-1;
LL ans=1e18;
while(qvq[k]<Top&&GET_K((u){qaq[s[k][qvq[k]]].x,qaq[s[k][qvq[k]]].y},(u){qaq[s[k][qvq[k]+1]].x,qaq[s[k][qvq[k]+1]].y})<id) ++qvq[k];
if(qvq[k]<=Top) ans=qaq[s[k][qvq[k]]].y-id*qaq[s[k][qvq[k]]].x+id*id;
if(l==r) return ans;
if(x<=mid) return min(ans,ask(l,mid,tl,x,id));
return min(ans,ask(mid+1,r,tr,x,id));
}
void add(int x,int y)
{
c[++num]=(p){h[x],y},h[x]=num;
}
int main()
{
n=read(),m=read(),C0=read();
for(int i=2,x;i<=n;++i)
{
qwq[i].fl=read(),fa[i]=read()+1,qwq[i].id=read(),add(fa[i],i);
if(!qwq[i].fl) qaq[qwq[i].id].x=2*(x=read()),read(),read(),qaq[qwq[i].id].y=1ll*x*x+read();
}
dfs();
for(int i=1;i<n;++i)
for(int j=0,l=L[i].size();j<l;++j)
if(L[i][j]<=R[i][j]) qu[++cnt]=(o){L[i][j],R[i][j],i};
sort(qu+1,qu+1+cnt);
for(int i=1;i<=cnt;++i)
change(1,n,1,qu[i].x,qu[i].y,qu[i].id);
for(int i=1;i<=m;++i)
Qu[i].x=id[read()+1],Qu[i].y=read(),Qu[i].id=i;
sort(Qu+1,Qu+1+m);
for(int i=1;i<=m;++i)
ans[Qu[i].id]=min(ask(1,n,1,Qu[i].x,Qu[i].y),(LL)(Qu[i].y*Qu[i].y+C0));
for(int i=1;i<=m;++i)
printf("%lld\n",ans[i]);
return 0;
}
