#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int INF = 1e9 + 7;
const int maxn = 1e5 + 5;
vector<pll> adj[maxn];
int a[maxn], b[maxn], ans[maxn];
int n;
int dep[maxn];
int cur_size = 1;
struct line{
int m, k;
line(){}
line(int _m, int _k) : m(_m), k(_k){}
int operator()(int x){
return m * x + k;
}
};
line st[maxn];
double intersect(line a, line b){
return double(a.k - b.k) / (b.m - a.m);
}
void dfs(int pos, int prev){
// cout<<pos<<" : \n";
// for(int i = 0; i < cur_size; i++) cout<<st[i].m<<" "<<st[i].k<<"\n";
if(pos){
int l = 0, r = cur_size - 1;
while(l < r){
int m = (l + r) / 2;
if(st[m](b[pos]) <= st[m + 1](b[pos])) r = m;
else l = m + 1;
}
ans[pos] = a[pos] + b[pos] * dep[pos] + st[l](b[pos]);
}
line cur = line(-dep[pos], ans[pos]);
int l = 0, r = cur_size - 1;
while(l < r){
int m = (l + r) / 2;
if(intersect(st[m], cur) >= intersect(st[m + 1], cur)){
// cout<<"kill : "<<m<<" "<<intersect(st[m], cur)<<" "<<intersect(st[m + 1], cur)<<"\n";
r = m;
}
else l = m + 1;
}
int prv_size = cur_size;
auto prv_line = st[l + 1];
cur_size = l + 2;
st[l + 1] = cur;
for(auto [x, w] : adj[pos]){
if(x == prev) continue;
dep[x] = dep[pos] + w;
dfs(x, pos);
}
cur_size = prv_size;
st[l + 1] = prv_line;
}
signed main(void){
fastio;
cin>>n;
for(int i = 0; i < n - 1; i++){
int a, b, w;
cin>>a>>b>>w;
a--, b--;
adj[a].eb(b, w);
adj[b].eb(a, w);
}
for(int i = 1; i < n; i++){
cin>>a[i]>>b[i];
}
dfs(0, -1);
for(int i = 1; i < n; i++) cout<<ans[i]<<" ";
cout<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5208 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5464 KB |
Output is correct |
| 3 |
Correct |
32 ms |
11956 KB |
Output is correct |
| 4 |
Correct |
47 ms |
15440 KB |
Output is correct |
| 5 |
Correct |
51 ms |
18152 KB |
Output is correct |
| 6 |
Correct |
63 ms |
21272 KB |
Output is correct |
| 7 |
Correct |
41 ms |
12116 KB |
Output is correct |
| 8 |
Correct |
79 ms |
16844 KB |
Output is correct |
| 9 |
Correct |
79 ms |
18504 KB |
Output is correct |
| 10 |
Correct |
72 ms |
17100 KB |
Output is correct |
