题解
设 (f_i) 为从点 (i) 走到点 (1) 的最小时间，那么有 (f_i=w_i+minlimits_{jin anc_i}{v_ioperatorname{dist}(i,j)+f_j})。
把 (operatorname{dist}) 拆开，就能写成一般的斜率优化形式。但如果对于每个点，都弹出单调栈末尾的不单调的决策，这个点的子树遍历完再把这些弹出的点放回单调栈里，那时间复杂度是错的。
考虑到对于每个点，实际上只需要更改单调栈内一个位置的值：二分出这个点在单调栈内应该插入的位置，并更改这个位置，然后更新单调栈长度即可。
代码
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T> void Read(T &x){
x=0;int _f=1;
char ch=getchar();
while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
x=x*_f;
}
template<typename T,typename... Args> void Read(T &x,Args& ...others){
Read(x);Read(others...);
}
typedef long long ll;
const int N=1e5+5;
int n,head[N],cntt=1;
struct Edge{int v,nxt;ll w;}e[N<<1];
void AddEdge(int u,int v,ll w){
e[++cntt]=Edge{v,head[u],w};head[u]=cntt;
}
ll f[N],w[N],v[N],dep[N];
bool Pop(int i,int j,int k){
return __int128((f[i]-f[j]))*(dep[j]-dep[k])>__int128((dep[i]-dep[j]))*(f[j]-f[k]);
}
int stk[N],tail=0;
void Dfs(int u,int fa){
if(tail>=1){
int l=1,r=tail;
while(l<r){
int mid=(l+r)>>1;
if(v[u]*(dep[stk[mid]]-dep[stk[mid+1]])>f[stk[mid]]-f[stk[mid+1]])
r=mid;
else
l=mid+1;
}
f[u]=w[u]+v[u]*(dep[u]-dep[stk[l]])+f[stk[l]];
}
int pre=tail,orig,ins;
if(tail>=1){
int l=2,r=tail+1;
while(l<r){
int mid=(l+r)>>1;
if(Pop(stk[mid-1],stk[mid],u)) r=mid;
else l=mid+1;
}
ins=tail=l;
}else ins=tail=1;
orig=stk[tail];stk[tail]=u;
for(int i=head[u];i;i=e[i].nxt){
if(e[i].v==fa) continue;
dep[e[i].v]=dep[u]+e[i].w;
Dfs(e[i].v,u);
}
stk[ins]=orig,tail=pre;
}
int main(){
Read(n);
For(i,1,n-1){
int u,v,w;Read(u,v,w);
AddEdge(u,v,w);AddEdge(v,u,w);
}
For(i,2,n) Read(w[i],v[i]);
Dfs(1,0);
For(i,2,n) printf("%lld ",f[i]);
return 0;
}