洛谷
我们可以考虑使用动态规划来解决。
在线性情况下，我们可以直接将状态设为 \(dp_i\) 表示走到 \(i\) 号点的时候的最小路程。
可以得到状态转移方程：
\[$
dp_i=\min(dp_j+(l_i-l_j)\times v_i+s_i)
$\]
其中 \(l_i\) 表示 \(i\) 号点到根节点的距离，可以直接预处理或者在深搜时处理。
此时我们的时间复杂度是 \(O(n^2)\) 无法通过，而且还需要转化为树状。
先考虑如何减小时间复杂度，我们会发现这条式子明显可以使用斜率优化。
由于每个节点选择值不具有单调性，我们不考虑使用单调队列，而是选择单吊栈和二分。
接着我们需要转为树状图，只需要在每一个节点的查询结束以后，将这个栈改为原本的情况即可。
但是由于我们维护的是一个单调栈，所以可能被删掉的数量会比较多，可能会超时。
所以我们再在单调栈里面二分出要删掉的位置，同时修改要修改位置的值和长度，并将被修改的值和原长度记录下来。
在回溯时，我们只需要再次修改长度和这个位置的值即可。
也就是说原数字仍然保留在栈中，但是不在范围内，所以不需要重新赋值。
最后注意在比较斜率时可能会超过爆掉。
代码：
/*
dp[i]=min(dp[j]+(l[i]-l[j])*v[i])+s[i]
x<y
y better
dp[x]-l[x]*v[i]>dp[y]-l[y]*v[i]
Y[x]=dp[x]
X[x]=l[x]
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,st[100005],top,s[100005],v[100005],dp[100005],x[100005],y[100005],l[100005],b[100005];
struct P{int x,y;
};
vector<P> e[100005];
bool check(int i,int j,int k){return (__int128)(y[i]-y[j])*(x[j]-x[k])<=(__int128)(y[j]-y[k])*(x[i]-x[j]);
}
int calc(int i,int j){return dp[j]+(l[i]-l[j])*v[i]+s[i];
}
pair<int,int> push(int x){int now=top,tmp,l=1,r=top;while(l<r){int mid=l+r>>1;if(check(x,st[mid+1],st[mid]))r=mid;else l=mid+1;}top=l;tmp=st[++top],st[top]=x;return {now,tmp};
}
void reset(int x,int y){st[top]=y;top=x;
}
int find(int v){int l=1,r=top;while(l<r){int mid=l+r>>1;if(calc(v,st[mid])>=calc(v,st[mid+1]))l=mid+1;else r=mid;}return st[l];
}void dfs(int p,int fa,int sum){l[p]=sum;dp[p]=calc(p,find(p));x[p]=l[p];y[p]=dp[p];pair<int,int> tmp2=push(p);for(P i:e[p])if(i.x!=fa)dfs(i.x,p,sum+i.y);reset(tmp2.first,tmp2.second);
}
signed main(){cin>>n;for(int i=1,a,b,c;i<n;i++){cin>>a>>b>>c;e[a].push_back({b,c});e[b].push_back({a,c});}for(int i=2;i<=n;i++)cin>>s[i]>>v[i];dfs(1,0,0);for(int i=2;i<=n;i++)cout<<dp[i]<<' ';return 0;
}