题意简述
初始有版本 \(0\)，其中仅包含点 \(0\)，且 \(c_0\) 给出，\(x_0=0\)。对于第 \(i\) 个版本，它依赖第 \(fr_i\) 个版本，而且会在父级版本的基础上进行以下两种操作之一：
- 插入一个新点，并且会给出 \(x_i\) 和 \(c_i\)。
- 删除一个本就存在的点（不为 \(0\)）
给出 \(m\) 次询问，每次给出 \(s,x\)，设版本 \(s\) 中包含的点构成的点集为 \(S\)，求 \(\min_{u\in S}(x-x_u)^2+c_u\)。
\(n,m\le 5\times10^5\)，数据保证所有插入操作时插入的点不相同（并不是很重要）。
分析
为了方便将初始下标置为 \(1\)。
根据各个版本的依赖关系我们可以建出一棵树。
发现其有加入删除操作，考虑用线段树分治去维护它，并用 dfn 序将树上问题转化为序列问题。
按照各个版本 dfn 序的顺序维护加点以及删点操作。具体来说，对于每个点维护 \(lst_i\) 表示 \(i\) 点最后一次插入时的 dfn 是多少。当有插入操作时，更新 \(lst_i\) 为当前点最后一次出现的 dfn。当遇到删除操作时，此时该点必定位于插入的版本的子树之内，此时该点会在 \([lst_i,dfn_i)\) 中出现，并会在 \([dfn_i,dfn_i+siz_i)\) 消失，并将 \(lst_i\) 更新为 \(dfn_i+siz_i\)。最后，（设 \(v\) 为插入 \(i\) 的版本）若有 \(lst_i\not=dfn_v+siz_v-1\)，则 \([lst_i,dfn_v+siz_v)\) 也会有点 \(i\) 出现（代码中用 \(lstlst_i\) 代替了 \(dfn_v+siz_v-1\)）。
接下来考虑如何计算最小贡献。考虑将其拆成斜率形式：
\(ans=(x-x_u)^2+c_u\rightarrow x^2-2xx_u+x_u^2+c_u=ans\rightarrow x_u^2+c_u=2xx_u+ans-x^2\)
这样，将 \((x_u,x_u^2+c_u)\) 视为决策点，\(2x\) 视为斜率，\(ans-x^2\) 视为截距，即可用凸包优化。
对于线段树上每个点用单调队列维护一个下凸壳，若在线询问则单调队列上二分找到最优决策点，时间复杂度 \(O(m\log^2n)\)；若离线将询问的 \(x\) 从小到大排序，则单调队列的队头只会向右移动，时间复杂度 \(O(m\log n)\)。
注意凸包的一个横坐标上只能有一个点，所以要特判多个决策点横坐标相同的情况。
点击查看代码
#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 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 calc(pii x,int y){
return x.se-2*y*x.fi+y*y;
}
bool operator<=(pii x,pii y){
return (double)((double)1.0*x.se)/((double)1.0*x.fi)<=(double)((double)1.0*y.se)/((double)1.0*y.fi);
}
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){
#define tl (int)q.size()-1
#define q d[p].q
if(!q.empty()&&q[tl].fi==x.fi){
if(x.se<=q[tl].se)q.pop_back();
else return;
}
while(tl>0&&(x-q[tl])<=(q[tl]-q[tl-1]))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
if(!q.empty()){
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;
}
int num[maxn];
bool cnmp(int x,int y){
return dfn[x]<dfn[y];
}
void solve_the_problem(){
n=rd(),Q=rd(),c[1]=rd();
rep(i,2,n){
int fa,z,y;
op[i]=rd(),fa=rd()+1,id[i]=rd()+1;
if(!op[i])a[id[i]]=rd(),y=rd(),z=rd(),c[id[i]]=rd();
G[fa].pb(i);
}
dfs(1);
rep(i,2,n)num[i]=i;
sort(num+2,num+n+1,cnmp);
rep(j,2,n){
int i=num[j];
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,2,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);
}
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){
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();
}
/*
*/