时空旅行（dfs序+线段树分治+斜率优化）

时空旅行

题意：

给定一棵以 $0$0为根的树，每个节点上有信息（一种是增加某个带权三维点，一种是删除某个带权三维点）；询问要求从根节点到某个节点的信息总和中找到一个最优带权三维点。

思路：

1. 首先，每个星球的 $y,z$y,z坐标显然是没用的。
2. 每个节点的信息原本的控制范围为其所在子树，如果将其处理成 $dfs$dfs序，则其控制的区间为数组上一个连续线段；这时我们考虑将这些线段利用线段树分治拆解开来(每个控制线段被拆解为 $log$log段)。
3. 需要注意的是，每个节点的信息中有些信息是删除某个点，这时我们只需要考虑将原控制线段拆成两段即可。
4. 将线段拆解并分布在线段树上后，在每个节点上都维护一个(下)凸包，见如下公式：
   花费： $cost=\left(x\right[i]-x{)}^2+c[i]$cost=(x[i]−x)2+c[i]
   变形为： $x[i{]}^2+c[i]=2\ast x\ast x[i]+cost-x^2$x[i]2+c[i]=2∗x∗x[i]+cost−x2
   若将每个带权点的选择看做一个决策，则决策所对应的直线方程中：
   给定直线斜率为 $k=2\ast x$k=2∗x
   每个决策点坐标为： $\left(x\right[i],x[i{]}^2+c\left[i\right])$(x[i],x[i]2+c[i])
   因此，在用这些决策点维护凸包时，需要先按照 $x$x坐标排序，再进行凸包的维护，也就是在将这些拆解后的线段放在线段树上时，要按照 $x$x坐标依次放。
5. 既然凸包已经维护好了，剩下就只有询问了，按照斜率优化的特点，询问也需要按照 $x$x坐标依次询问，才能保证复杂度。

代码

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline ll read() {ll x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
 
const int maxn = 5e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;

int n, m;
int head[maxn], to[maxn], nxt[maxn], tot;
int p[maxn], id[maxn], ID;
int ft[maxn<<2], tl[maxn<<2];
ll x[maxn], c[maxn], ans[maxn];
vector<int> L[maxn], R[maxn], P[maxn<<2], s[maxn<<2];
struct Query{
    int x, pos, id;
    bool operator < (const Query &rhs) const {
        return x<rhs.x;
    }
}q[maxn];

inline bool cmp(int i, int j) { return x[i]<x[j]; }

inline void add_edge(int u, int v) {
    ++tot; to[tot]=v; nxt[tot]=head[u]; head[u]=tot;
}

void dfs(int u) {
    id[u]=++ID;
    if(p[u]>=0) L[p[u]].push_back(ID);
    else R[-p[u]].push_back(ID-1);
    for(int i=head[u]; i; i=nxt[i]) dfs(to[i]);
    if(p[u]>=0) R[p[u]].push_back(ID);
    else L[-p[u]].push_back(ID+1);
}

double slope(int i, int j) {
    double x1=x[i], y1=x[i]*x[i]+c[i];
    double x2=x[j], y2=x[j]*x[j]+c[j];
    if(fabs(x1-x2)<1e-9) return y2>=y1?1e18:-1e18;
    return (y2-y1)/(x2-x1);
}

void update(int x, int y, int i, int l, int r, int now) {
    if(x<=l&&r<=y) {
        while(ft[now]<tl[now]&&slope(s[now][tl[now]-1],s[now][tl[now]])>=slope(s[now][tl[now]],i)) tl[now]--, s[now].pop_back();
        s[now].push_back(i); tl[now]++;
        return;
    }
    int m=(l+r)/2;
    if(x<=m) update(x,y,i,l,m,now<<1);
    if(y>m) update(x,y,i,m+1,r,now<<1|1);
}

void query(int x, int pos, int id, int l, int r, int now) {
    while(ft[now]<tl[now]&&slope(s[now][ft[now]],s[now][ft[now]+1])<=2*x) ft[now]++;
    if(ft[now]<=tl[now]) {
        int j=s[now][ft[now]];
        ans[id]=min(ans[id],(::x[j]-x)*(::x[j]-x)+c[j]);
    }
    if(l==r) return;
    int m=(l+r)/2;
    if(pos<=m) query(x,pos,id,l,m,now<<1);
    else query(x,pos,id,m+1,r,now<<1|1);
}

int main() {
    memset(tl,-1,sizeof(tl));
    n=read(), m=read(), c[0]=read();
    p[0]=0;
    for(int i=1; i<n; ++i) {
        int op=read();
        if(op==0) {
            int f=read(), id=read(); x[id]=read();
            int y=read(), z=read();  c[id]=read();
            p[i]=id; add_edge(f,i);
        }
        else {
            int f=read(), id=-read();
            p[i]=id; add_edge(f,i);
        }
    }
    dfs(0);
    vector<int> a(n);
    for(int i=0; i<n; ++i) a[i]=i;
    sort(a.begin(),a.end(),[&](int i,int j){return x[i]<x[j];});
    for(int i=0; i<n; ++i)
        for(int j=0; j<L[a[i]].size(); ++j) if(L[a[i]][j]<=R[a[i]][j])
            update(L[a[i]][j],R[a[i]][j],a[i],1,n,1);
    for(int i=1; i<=m; ++i) {
        int s=read(), x0=read();
        q[i]=(Query){x0,id[s],i};
    }
    sort(q+1,q+1+m);
    for(int i=1; i<=m; ++i) ans[q[i].id]=1e18, query(q[i].x,q[i].pos,q[i].id,1,n,1);
    for(int i=1; i<=m; ++i) printf("%lld\n", ans[i]);
}