P2305 [NOI2014] 购票
设 \(f_{x}\) 表示从 \(x\) 点跳到 \(1\) 的最少费用。考虑 \(x\) 的一个祖先 \(u\)，有
\[f_x=f_{u}+\text{dis}_{u,x}\times p_x+q_x \]其中需要满足 \(\text{dis}_{u,x}\le l_x\)。
由于 \(p\) 为 \(x\) 的祖先，考虑前缀和来化简 \(\text{dis}_{u,x}\)。记 \(\text{pre}_x\) 表示根节点 \(1\) 到 \(x\) 的简单路径长度。则有 \(\text{dis}_{u,x}=\text{pre}_x-\text{pre}_p\)。带入原式并化简得到
\[f_{x}=f_u+\text{pre}_x\times p_x-\text{pre}_u\times p_x+q_x \]将 \(-\text{pre}_u\) 看作 \(k\)，容易得到斜率优化的形式。
由于需要满足条件 \(\text{pre}_x-\text{pre}_p \le l_x\)，考虑外层套用线段树，则内层使用李超线段树实现较为简单。
由于需要找到点的祖先节点区间，线段树遍历顺序采用原树的出栈序。
至此，可以得到一个线段树套李超线段树的 \(\mathcal{O}(n \log^2 n)\) 的做法，可以通过。
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>inline bool read(T &x){
x=0;
char ch=getchar();
bool flag=0,ret=0;
while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
x=flag?-x:x;
return ret;
}
template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
return read(a)&&read(args...);
}
template<typename T>void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
if(x<0) putchar('-'),x=-x;
prt(x);
putchar(ch);
}
template<typename T,typename ...Args>inline void put(T a,Args ...args){
put(a);
put(args...);
}
template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
put(ch,a);
put(ch,args...);
}
inline void put(string s){
for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
}
inline void put(const char* s){
for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
}
}
using namespace IO;
#define N 200005
#define M 1000005
#define Maxn 1000000
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
int n,typ,cnt,head[N],num;
struct object{
ll f,s,p,q,l;
}a[N];
struct edge{
int v,nxt;
}e[N<<1];
inline void add(int u,int v){
e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
struct line{
ll k,b;
}L[N];
inline int insert(ll k,ll b){
L[++num]=(line){k,b};
return num;
}
inline ll calc(int id,ll x){
return L[id].k*x+L[id].b;
}
struct LC_Tree{
struct node{
int ls,rs,s;
}t[M*30];
#define lc(x) t[x].ls
#define rc(x) t[x].rs
#define s(x) t[x].s
int Idx;
inline void update(int &x,int l,int r,int pos){
if(!x) return t[x=++Idx].s=pos,void();
int mid=l+r>>1;
if(calc(s(x),mid)>calc(pos,mid)) swap(s(x),pos);
if(calc(s(x),l)>calc(pos,l)) update(lc(x),l,mid,pos);
if(calc(s(x),r)>calc(pos,r)) update(rc(x),mid+1,r,pos);
}
inline ll query(int x,int l,int r,int pos){
if(!x) return inf;
ll res=calc(s(x),pos);
int mid=l+r>>1;
if(pos<=mid) res=min(res,query(lc(x),l,mid,pos));
else res=min(res,query(rc(x),mid+1,r,pos));
return res;
}
#undef lc
#undef rc
#undef s
}T;
int rt[N<<2];
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
inline void update(int x,int l,int r,int pos,int k){
T.update(rt[x],0,Maxn,k);
if(l==r) return;
int mid=l+r>>1;
if(pos<=mid) update(lc(x),l,mid,pos,k);
else update(rc(x),mid+1,r,pos,k);
}
inline ll query(int x,int l,int r,int ql,int qr,int k){
if(ql<=l&&qr>=r) return T.query(rt[x],0,Maxn,k);
ll res=inf;
int mid=l+r>>1;
if(ql<=mid) res=min(res,query(lc(x),l,mid,ql,qr,k));
if(qr>mid) res=min(res,query(rc(x),mid+1,r,ql,qr,k));
return res;
}
#undef lc
#undef rc
ll f[N],pre[N];
int id[N],idx,tp,c[N];
inline void prework(int x){
for(int i=head[x];i;i=e[i].nxt) prework(e[i].v);
id[x]=++idx;
}
inline void dfs(int x){
update(1,1,n,id[x],insert(-pre[tp],f[x]));
c[tp]=x;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
tp++;
pre[tp]=pre[tp-1]+a[v].s;
int L=id[v],R=id[c[lower_bound(pre,pre+tp,pre[tp]-a[v].l)-pre]];
f[v]=query(1,1,n,L,R,a[v].p)+pre[tp]*a[v].p+a[v].q;
dfs(v),c[tp]=0,tp--;
}
}
int main(){
read(n,typ);
for(int i=2;i<=n;i++)
read(a[i].f,a[i].s,a[i].p,a[i].q,a[i].l),add(a[i].f,i);
prework(1),dfs(1);
for(int i=2;i<=n;i++) put('\n',f[i]);
return 0;
}