#include<bits/stdc++.h>
#define int long long
using namespace std;
inline bool _u(char x){return x>='0'&&x<='9';}
inline int read(){
int x,f;
char ch=getchar();
for(f=1;!_u(ch);ch=='-'&&(f=-1),ch=getchar());
for(x=0;_u(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());
return x*f;
}
inline void write(int num){
static int st[39],tp=0;
num<0&&(putchar('-'),num=-num);
do st[++tp]=num%10; while(num/=10);
while(tp) putchar(st[tp--]|48);
return;
}
const int N=1e5+10;
//dp[u]=s[u]+min(v[u]*(dep[u]-dep[f])+dp[f])
//dp[u]=s[u]+v[u]*dep[u]+min(dp[f]-v[u]*dep[f])
int dp[N],dep[N];
int st[N],tp;
int s[N],v[N];
vector<pair<int,int> > e[N];
inline bool check(int x,int y,int z){
return (long double)(dp[y]-dp[x])*(dep[z]-dep[y])>(long double)(dp[z]-dp[y])*(dep[y]-dep[x]);
}
inline bool fyn(int x,int y,int z){
return dp[x]-dp[y]<z*(dep[x]-dep[y]);
}
void dfs(int u,int f){
#define MID(l,r) (((r-l)>>1)+l)
if(tp){
int l,r,mid;
for(l=1,r=tp;l<r;){
if(mid=MID(l,r),fyn(st[mid],st[mid+1],v[u])) r=mid;
else l=mid+1;
}
dp[u]=s[u]+(dep[u]-dep[st[l]])*v[u]+dp[st[l]];
}
int l,r,mid;
if(1<tp && !check(st[tp-1],st[tp],u)) r=tp;
else
for(l=1,r=tp;l<r;){
if(mid=MID(l,r),check(st[mid],st[mid+1],u)) r=mid;
else l=mid+1;
}
int fy=tp,ffy=st[tp=r+1];
st[tp]=u;
for(int i=0,to,val;i<e[u].size();++i){
tie(to,val)=e[u][i];
if(to!=f){
dep[to]=dep[u]+val;
dfs(to,u);
}
}
st[tp]=ffy;
tp=fy;
#undef MID
}
int n;
signed main(){
// freopen("har.in","r",stdin);
// freopen("har.out","w",stdout);
n=read();
for(int i=1,u,v,w;i<n;++i)
u=read(),v=read(),w=read(),e[u].emplace_back(v,w),e[v].emplace_back(u,w);
for(int i=2;i<=n;++i)
s[i]=read(),v[i]=read();
dfs(1,0);
for(int i=2;i<=n;++i) write(dp[i]),putchar(i==n?'\n':' ');
return(0-0);
}
/*
5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30
*/
Compilation message
harbingers.cpp: In function 'void write(long long int)':
harbingers.cpp:14:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
14 | num<0&&(putchar('-'),num=-num);
| ~~~^~~~~
harbingers.cpp: In function 'void dfs(long long int, long long int)':
harbingers.cpp:51:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i=0,to,val;i<e[u].size();++i){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
24 ms |
11100 KB |
Output is correct |
| 4 |
Correct |
34 ms |
14172 KB |
Output is correct |
| 5 |
Correct |
39 ms |
17084 KB |
Output is correct |
| 6 |
Correct |
47 ms |
20068 KB |
Output is correct |
| 7 |
Correct |
22 ms |
11868 KB |
Output is correct |
| 8 |
Correct |
60 ms |
15840 KB |
Output is correct |
| 9 |
Correct |
58 ms |
17092 KB |
Output is correct |
| 10 |
Correct |
55 ms |
16328 KB |
Output is correct |
