#include<bits/stdc++.h>
#define fi first
#define se second
#define ull unsigned long long
#define ll long long
#define BIT(a , b) (((a) >> (b)) & 1)
#define flip(a , b) ((a) ^ (1 << (b)))
#define pii pair<int, int>
#define pb push_back
#define nl cout << "\n";
#define __ <<" "<<
#define mem(a, b) memset((a), (b), sizeof((a)))
#define all(c) (c).begin(), (c).end()
#define add(x , y) ((x) + (y) >= mod ? ((x) + (y) - mod) : ((x) + (y)))
#define file "harbingers"
#define Times cerr << "\nTime run: " << clock() / 1000.0 << " ms\n";
using namespace std;
const ll oo = 2e18 + 7;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const int LOG = 20;
const int base = 31;
void run_with_file(){
if(fopen(file".in" , "r")){
freopen(file".in", "r" , stdin);
freopen(file".out", "w" , stdout);
}
}
int n;
vector <pii> adj[N];
ll s[N] , v[N];
ll dp[N];
struct line_container{
struct line{
ll a , b;
int id;
ll cal(ll x){
return a * x + b;
}
};
vector <line> vt;
ll intersect(line l1 , line l2){
// assert(l1.a - l2.a == 0);
return (l2.b - l1.b) / (l1.a - l2.a);
}
void add_line(line l3){
if(vt.size() < 2) return vt.pb(l3) , void();
line l2 = vt.back();
vt.pop_back();
line l1 = vt.back();
while(vt.size() >= 2 && intersect(l3 , l1) < intersect(l2 , l1)){
l2 = vt.back();
vt.pop_back();
l1 = vt.back();
}
if(intersect(l3 , l1) < intersect(l2 , l1)){
vt.push_back(l3);
}
else{
vt.push_back(l2);
vt.push_back(l3);
}
}
ll search(ll x){
int l = 0;
int r = (int) vt.size() - 1;
while(l <= r){
int mid = (l + r) >> 1;
ll lef , rig;
if(mid == (int)vt.size() - 1) rig = oo;
else rig = intersect(vt[mid] , vt[mid + 1]);
if(mid == 0) lef = -oo;
else lef = intersect(vt[mid] , vt[mid - 1]);
if(x > rig) l = mid + 1;
if(x < lef) r = mid - 1;
if(lef <= x && x <= rig) return vt[mid].cal(x);
}
return 0;
}
} cht;
void dfs(int i , int p , ll dis){
// cout << i << '\n';
for(auto it : adj[i]){
int j = it.fi;
int w = it.se;
if(j == p) continue;
dp[j] = cht.search(v[j]) + (dis + w) * v[j] + s[j];
cht.add_line({-dis - w , dp[j] , j});
dfs(j , i , dis + w);
// cout << cht.vt.size() << '\n';
// cout << i << '\n';
// for(auto j : cht.vt) cout << j.a << ' ' << j.b << ' ' << j.id << "/ ";
// nl;
if(cht.vt.size()) if(cht.vt.back().id == j) cht.vt.pop_back();
}
}
void inp(){
cin >> n;
for(int i = 1 ; i < n ; i++){
int u , v , w;
// u = i;
// v = u + 1;
// w = 10000;
cin >> u >> v >> w;
adj[u].pb({v , w});
adj[v].pb({u , w});
}
for(int i = 2 ; i <= n ; i++){
cin >> s[i] >> v[i];
// s[i] = 1000000000;
// v[i] = 1000000000;
}
}
void solve(){
cht.vt.pb({0 , 0 , 1});
dfs(1 , 0 , 0);
for(int i = 2 ; i <= n ; i++) cout << dp[i] << ' ';
}
int main(){
cin.tie(0)->sync_with_stdio(false);
run_with_file();
int test_case = 1;
//cin >> test_case;
while(test_case--){
inp();
solve();
}
}
/* UwU */
Compilation message
harbingers.cpp: In function 'void run_with_file()':
harbingers.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | freopen(file".in", "r" , stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | freopen(file".out", "w" , stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9564 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
10076 KB |
Output isn't correct |
| 3 |
Incorrect |
35 ms |
18756 KB |
Output isn't correct |
| 4 |
Incorrect |
48 ms |
23500 KB |
Output isn't correct |
| 5 |
Incorrect |
65 ms |
26856 KB |
Output isn't correct |
| 6 |
Incorrect |
68 ms |
30740 KB |
Output isn't correct |
| 7 |
Incorrect |
43 ms |
17236 KB |
Output isn't correct |
| 8 |
Incorrect |
69 ms |
22316 KB |
Output isn't correct |
| 9 |
Incorrect |
73 ms |
24848 KB |
Output isn't correct |
| 10 |
Incorrect |
68 ms |
24132 KB |
Output isn't correct |
