题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=1767
题解：
斜率优化DP，单调栈，二分
定义 DP[i] 表示从 i 节点出发，到达根所花的最少时间。
同时既然是一棵树，那么裸的转移还是比较容易想出来的。
$DP[i]=min(DP[j]+(dis_i-dis_j)V_i)+W_i (j是i到根的链上的节点)$
$\quad=min(DP[j]-dis_j*V_i)+dis_i*V_i+W_i$
其中 dis[i] 表示 i 节点到根的距离。
转移方程的意思就是i号点的邮递员走到j号点，然后j号点的邮递员继续走向根。
考虑优化：
假设对于当前计算的DP[i],有两个转移来源点：k,j，同时dis[k]<dis[j],设j点比k点优。
那么有：$DP[j]-dis_j*V_i-(DP[k]-dis_k*V_i)<0$
则: $\frac{DP[j]-DP[k]}{dis[j]-dis[k]}<V[i]$
如果令 Slope(j,k)=$\frac{DP[j]-DP[k]}{dis[j]-dis[k]}$
那么得到结论，如果 dis[k]<dis[j],且Slope(j,k)<V[i]的话，则j点优于k点。
同时如果存在三个转移来源点：k,j,i，满足dis[k]<dis[j]<dis[i]，
同时Slope(i,j)<Slope(j,k),则j点无效。
所以对于每个来源点二元组(dis[j],DP[j])，只需要在平面上维护一个下凸壳即可。
值得注意的地方：
1).注意到DP时是在DFS遍历树时进行，所以这就保证了dis的单调递增，
但是V[i]却不单调，所以要用单调栈一个下凸壳，并在其中二分最优转移来源点。
2).由于是在树上进行，所以从某个节点回溯之后，要把当时它插入单调栈时造成的影响消除。
具体做法是：
进入该节点时（已经计算出其DP值）
二分当前点应该在单调栈中插入的位置p，记录该位置之前的信息以及栈顶位置，
然后直接把该点放在p位置，并将栈顶移到p位置。
离开该节点时，再把之前修改的东西全部复原(还原单调栈中p位置的信息，还原栈顶位置)。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 100050
#define ll long long
using namespace std;
ll W[MAXN],V[MAXN],DP[MAXN],dis[MAXN];
int N;
struct Edge{
int to[MAXN*2],val[MAXN*2],nxt[MAXN*2],head[MAXN],ent;
Edge(){ent=2;}
void Adde(int u,int v,int w){
to[ent]=v; val[ent]=w; nxt[ent]=head[u]; head[u]=ent++;
to[ent]=u; val[ent]=w; nxt[ent]=head[v]; head[v]=ent++;
}
}E;
struct Mostk{
int s[MAXN],top;
#define Slope(i,j) (1.0*(DP[i]-DP[j])/(dis[i]-dis[j]))
void Reset(){top=0;}
int Find(int i){
static int l,r,mid,ret;
l=2; r=top; ret=top+1;
if(top&&dis[i]==dis[s[top]])
{if(DP[i]<DP[s[top]]) ret=top,r--; else return 0;}
while(l<=r){
mid=(l+r)>>1;
if(Slope(i,s[mid])<Slope(s[mid],s[mid-1])) ret=mid,r=mid-1;
else l=mid+1;
}
return ret;
}
int Query(int i){
static int l,r,mid,ret;
l=2; r=top; ret=1;
while(l<=r){
mid=(l+r)>>1;
if(Slope(s[mid],s[mid-1])>V[i]) r=mid-1;
else ret=mid,l=mid+1;
}
return s[ret];
}
}S;
void DFS(int u,int fa){
int p,oldp,oldsp,oldtop;
oldp=p=S.Find(u);
if(p) oldsp=S.s[p],S.s[p]=u,oldtop=S.top,S.top=p;
for(int i=E.head[u];i;i=E.nxt[i]){
int v=E.to[i]; if(v==fa) continue;
dis[v]=dis[u]+E.val[i];
p=S.Query(v);
DP[v]=DP[p]+(dis[v]-dis[p])*V[v]+W[v];
DFS(v,u);
}
if(oldp) S.s[oldp]=oldsp; S.top=oldtop;
}
int main(){
scanf("%d",&N);
for(int i=1,u,v,w;i<N;i++){
scanf("%d%d%d",&u,&v,&w);
E.Adde(u,v,w);
}
for(int i=2;i<=N;i++)
scanf("%lld%lld",&W[i],&V[i]);
S.Reset();
DFS(1,0);
for(int i=2;i<=N;i++)
printf(i<N?"%lld ":"%lld",DP[i]);
return 0;
}