题目链接
题意分析
这是一道树上斜率优化题
首先
\[dp[i]=min\{dp[j]+(dis[i]-dis[j])* p[i]+q[i]\}(j∈Pre_i)
\]
\]
那么就是
\[p[i]=\frac{dp[i]-dp[j]}{dis[i]-dis[j]}
\]
\]
我们根据\(p[i]\)递增可知
我们需要使用单调队列维护下凸包
但是由于是树 所以我们不可以进行一般的单调队列维护
所以这里我们只好进行暴力二分出最优的位置了
毕竟单调队列实现起来不是真正的删除 而是头尾指针的移动 以及唯一的取代
然后我们会回溯时恢复指针以及取代值就可以了
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 1008611
#define IL inline
#define M 1008611
#define D double
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
T __=0,___=1;char ____=getchar();
while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
_=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
ll n,tot,ans,head,tail;
ll to[N],nex[N],lat[N],w[N];
ll fa[N],p[N],q[N];
ll dis[N],dp[N],que[N];
IL void add(ll x,ll y,ll z)
{to[++tot]=y;nex[tot]=lat[x];lat[x]=tot;w[tot]=z;}
IL D cdy(int x,int y){return dis[y]-dis[x];}
IL D wzy(int x,int y){return dp[y]-dp[x];}
IL void dfs(ll now,ll fat)
{
ll now_cdy=head,now_wzy=tail;
ll le=now_cdy,ri=now_wzy-2,ans=-1;
while(le<=ri)
{
ll mid=(le+ri)>>1;
if(wzy(que[mid],que[mid+1])>=p[now]*cdy(que[mid],que[mid+1])) ri=mid-1,ans=mid;
else le=mid+1;
}
if(ans!=-1) head=ans;
else head=tail-1;
dp[now]=dp[que[head]]+(dis[now]-dis[que[head]])*p[now]+q[now];
le=head;ri=tail-2;ans=-1;
while(le<=ri)
{
ll mid=(le+ri)>>1;
if(wzy(que[mid],que[mid+1])*cdy(que[mid+1],now)<=wzy(que[mid+1],now)*cdy(que[mid],que[mid+1])) ans=mid,le=mid+1;
else ri=mid-1;
}
if(ans!=-1) tail=ans+2;
else tail=head+1;
ll fro=que[tail];que[tail++]=now;
for(R ll i=lat[now];i;i=nex[i])
{
ll v=to[i];
if(v==fat) continue;
dis[v]=dis[now]+w[i];
dfs(v,now);
}
head=now_cdy;que[tail-1]=fro;tail=now_wzy;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);
for(R ll i=2,x,y;i<=n;++i)
{
read(x);read(y);
add(x,i,y);
read(p[i]);read(q[i]);
}
for(R ll i=lat[1];i;i=nex[i])
{
ll v=to[i];
dis[v]=w[i];
que[head=0]=1;tail=1;
dfs(v,1);
}
for(R ll i=2;i<=n;++i)
printf("%lld\n",dp[i]);
// fclose(stdin);
// fclose(stdout);
return 0;
}