#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
using lf=long double;
constexpr int N=1e5+5;
int n,eh[N],ec;
struct{int nxt,to,dis;}e[N<<1];
int s[N],v[N];
long long dep[N],f[N];
void adde(int u,int v,int w){
e[++ec]={eh[u],v,w},eh[u]=ec;
}
long long X(int u){return dep[u];}
long long Y(int u){return f[u];}
lf slope(int a,int b){
return 1.0l*(Y(a)-Y(b))/(1.0*(X(a)-X(b)));
}
bool del(int a,int b,int c){
// 判断 b 前后分别是 a 和 b 时 b 是否被删除
return slope(a,b)>=slope(b,c);
}
bool cmp(long long kk,int a,int b){
// a 是否不劣于 b
return slope(a,b)>=kk;
}
struct UndoStack{
struct Info{
// 记录对 q 数组的一次(真实的)修改操作用于撤销
int p,ot,ov;
Info(int p,int ot,int ov):p{p},ot{ot},ov{ov}{};
};
int top;
int q[N];
stack<Info> rec;
void push(int v){
int l{1},r{top};
while(l<r){
int mid{(l+r)>>1};
if(mid==top||del(q[mid],q[mid+1],v)) r=mid;
else l=mid+1;
}
int res{l};
++res;
rec.emplace(res,top,q[res]);
q[top=res]=v;
}
void undo(){
auto t=rec.top();rec.pop();
top=t.ot,q[t.p]=t.ov;
}
int query(long long kk)const{
int l{1},r{top};
while(l<r){
int mid((l+r)>>1);
if(mid==top||cmp(kk,q[mid],q[mid+1])) r=mid;
else l=mid+1;
}
return q[l];
}
}qq;
void dfs(int u,int fa){
if(u==1) f[u]=0;
else{
int x=qq.query(v[u]);
f[u]=1ll*v[u]*(dep[u]-dep[x])+s[u]+f[x];
}
qq.push(u);
for(int i(eh[u]);i;i=e[i].nxt){
int v{e[i].to},w{e[i].dis};
if(v==fa) continue;
dep[v]=dep[u]+w;
dfs(v,u);
}
qq.undo();
}
signed main(){
scanf("%d",&n);
for(int i{1};i<n;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
adde(u,v,w),adde(v,u,w);
}
for(int i{2};i<=n;++i){
scanf("%d%d",s+i,v+i);
}
dfs(1,0);
for(int i(2);i<=n;++i)
printf("%lld%c",f[i]," \n"[i==n]);
return 0;
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
harbingers.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d%d%d",&u,&v,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~
harbingers.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%d%d",s+i,v+i);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
38 ms |
9144 KB |
Output is correct |
| 4 |
Correct |
62 ms |
12112 KB |
Output is correct |
| 5 |
Correct |
58 ms |
14784 KB |
Output is correct |
| 6 |
Correct |
63 ms |
17716 KB |
Output is correct |
| 7 |
Correct |
40 ms |
9140 KB |
Output is correct |
| 8 |
Correct |
104 ms |
12928 KB |
Output is correct |
| 9 |
Correct |
115 ms |
14544 KB |
Output is correct |
| 10 |
Correct |
97 ms |
13420 KB |
Output is correct |
