题意
给定一颗树，树中每个结点有一个邮递员，每个邮递员要沿着唯一的路径走向capital(1号结点)，每到一个城市他可以有两种选择： 1.继续走到下个城市 2.让这个城市的邮递员替他出发。 每个邮递员出发需要一个准备时间W[I]，他们的速度是V[I]，表示走一公里需要多少分钟。 现在要你求出每个城市的邮递员到capital的最少时间(不一定是他自己到capital，可以是别人帮他）
思路
如果是一条链的话，预处理出路径的前缀和(D)
有以下DP转移方程
[f(i)=min(f(j)+W_i+V_i(D_i-D_j)
]
去掉min,转换一下
[f(j)=V_iD_j+f(i)-W_i-V_iD_i
]
这就可以斜率优化了，不过因为(V_i)并不单增，我们需要在单调栈中维护整个下凸壳，通过二分来找到最优决策点
接着放在树上，问题在于我们如何来维护单调栈。如果每一次还原被修改的元素，时间复杂度会达到(O(n^2))。实际上我们可以通过可持久化数组 或 对单调栈的弹出魔改 来实现
这里讲第二种实际上是第一种懒得写对于每一次弹出的数，只挪指针，最后插入节点时将该插入位置原本的元素记录，回溯回来时还原即可
心得
自己的二分是真得差，都是看得别人的，其实就是将(mid)带入成要求的点即可
代码
#include <bits/stdc++.h>
#define N 220000
#define inf 998244353
using namespace std;
int n,tot,to[N],nex[N],head[N],st[N],top;
long long f[N],dis[N],s[N],val[N];
double t[N];
void add(int u,int v,long long w){
to[++tot]=v;nex[tot]=head[u];
head[u]=tot;val[tot]=w;
}
double k(int x,int y){
if(dis[y]==dis[x]) return 0;
double xx=(dis[y]-dis[x]),yy=(f[y]-f[x]);
return yy/xx;
}
int query(int x){
int L=1,R=top,mid;
while(L<=R){
mid=L+R>>1;
if(k(st[mid],st[mid+1])<t[x]) L=mid+1;
else if(k(st[mid-1],st[mid])>t[x]) R=mid-1;
else return mid;
}return mid;
}
int modify(int x){
int L=1,R=top,mid;
while(L<=R){
mid=L+R>>1;
if(k(st[mid],st[mid+1])<k(st[mid],x)) L=mid+1;
else if(k(st[mid-1],st[mid])>k(st[mid-1],x)) R=mid-1;
else return mid;
}return mid;
}
void dfs(int u,int fa){
int x=query(u),ttop,i;long long vval;
f[u]=f[st[x]]+(dis[u]-dis[st[x]])*t[u]+s[u];
x=modify(u);ttop=top;vval=st[x+1];st[top=x+1]=u;
for(i=head[u];i;i=nex[i]){
int v=to[i];if(v==fa) continue;
dis[v]=dis[u]+val[i];dfs(v,u);
}top=ttop;st[x+1]=vval;
}
int main(){
int i,j;scanf("%d",&n);
for(i=1;i<n;i++){
int u,v;long long w;
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w);add(v,u,w);
}for(i=2;i<=n;i++) scanf("%lld%lf",&s[i],&t[i]);
dfs(1,0);for(i=2;i<=n;i++) printf("%lld%s",f[i],i==n?"
":" ");
return 0;
}