显然的斜率优化
第一眼想到的是用可持久化数组维护单调栈
但是觉得懒得写就放弃了
点分治后用重心向上的链更新重心子树
感觉也可以看做树上一样的东西
代码写的很丑
#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define poly vector<int>
#define bg begin
cs int RLEN=1<<20|1;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ib==ob)?EOF:*ib++;
}
inline int read(){
char ch=gc();
int res=0;bool f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
inline ll readl(){
char ch=gc();
ll res=0;bool f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=200005;
int adj[N],nxt[N<<1],to[N<<1],cnt;
ll val[N<<1],dep[N],li[N],qv[N],f[N];
int n,fa[N],p[N],siz[N],rt,sizrt,maxn,vis[N];
inline void addedge(int u,int v,ll w){
nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,val[cnt]=w;
}
void dfs1(int u){
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
dep[v]=dep[u]+val[e],dfs1(v);
}
}
struct pt{
long double x,y;
pt(long double _x=0,long double _y=0):x(_x),y(_y){}
friend inline pt operator +(cs pt &a,cs pt&b){
return pt(a.x+b.x,a.y+b.y);
}
friend inline pt operator -(cs pt &a,cs pt &b){
return pt(a.x-b.x,a.y-b.y);
}
friend inline long double operator *(cs pt &a,cs pt&b){
return a.x*b.y-a.y*b.x;
}
};
pt stk[N];
int q[N],tot,top;
void getrt(int u){
siz[u]=1;int son=0;
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
if(vis[v])continue;
getrt(v),siz[u]+=siz[v];
chemx(son,siz[v]);
}
chemx(son,maxn-siz[u]);
if(son<=sizrt)sizrt=son,rt=u;
}
void getall(int u){
q[++tot]=u;
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
if(vis[v])continue;
getall(v);
}
}
struct comp{
inline bool operator ()(cs int &a,cs int &b){
return dep[a]-li[a]>dep[b]-li[b];
}
};
inline void push_(int u){
pt now=pt(dep[u],f[u]);
while(top>1&&(now-stk[top])*(now-stk[top-1])<=0)top--;
stk[++top]=now;
}
inline pt query(int u){
int l=1,r=top-1,res=top;pt ret;
while(l<=r){
int mid=(l+r)>>1;
ret=(stk[mid]-stk[mid+1]);
if(ret.y<=ret.x*p[u])res=mid,r=mid-1;
else l=mid+1;
}
return stk[res];
}
inline void trans(int u,pt xx){
chemn(f[u],(int)(xx.y+0.5)+(dep[u]-(int)(xx.x+0.5))*p[u]+qv[u]);
}
void solve(int u,int ss){
if(ss==1)return;
maxn=ss,sizrt=n;
getrt(u);
int now=rt;
for(int e=adj[now];e;e=nxt[e])vis[to[e]]=1,ss-=siz[to[e]];
solve(u,ss),tot=0;
for(int e=adj[now];e;e=nxt[e])getall(to[e]);
sort(q+1,q+tot+1,comp());
int x=now;top=0;
for(int i=1;i<=tot;i++){
int v=q[i];
while(x!=fa[u]&&dep[x]>=dep[v]-li[v])push_(x),x=fa[x];
if(top)trans(v,query(v));
}
for(int e=adj[now];e;e=nxt[e])solve(to[e],siz[to[e]]);
}
signed main(){
#ifdef Stargazer
freopen("lx.cpp","r",stdin);
#endif
n=read(),read();
for(int i=2;i<=n;i++){
fa[i]=read();
addedge(fa[i],i,readl());
p[i]=read(),qv[i]=read(),li[i]=read();
}
memset(f,127/3,sizeof(f)),f[1]=0;
vis[1]=1;dfs1(1);
solve(1,n);
for(int i=2;i<=n;i++)cout<<f[i]<<'
';
}