// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
//#define task "A"
#define ll long long
#define endl '\n'
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
struct Point{
ll x, y;
Point(){};
Point(ll x, ll y) : x(x), y(y){};
};
ll sz = 1;
vector<pair<ll, ll>> node[N];
Point line[N];
long double Intersex(Point l1, Point l2){
return (l2.y - l1.y) * 1.0 / (l1.x - l2.x);
}
bool chk(Point lnow, Point l1, Point l2){
return (Intersex(lnow, l2) <= Intersex(l1, l2));
}
ll add(Point m){
ll l = 2, h = sz;
while (l <= h){
ll mid = (l + h) >> 1;
Point l1 = line[mid];
Point l2 = line[mid - 1];
if (chk(m, l1, l2)) h = mid - 1;
else l = mid + 1;
}
return l;
}
ll get(Point x, ll now){
return x.x * now + x.y;
}
ll query(ll x){
ll l = 1, h = sz - 1;
while (l <= h){
ll mid = (l + h) >> 1;
if (get(line[mid], x) <= get(line[mid + 1], x)) l = mid + 1;
else h = mid - 1;
}
return get(line[l], x);
}
ll dp[N], a[N], b[N], dep[N];
void dfs(ll u, ll p){
ll tmp = sz;
ll id;
Point tmpP;
if (p){
dp[u] = a[u] + dep[u] * b[u] - query(b[u]);
Point cur = {dep[u], -dp[u]};
id = add(cur);
tmpP = line[id];
sz = id;
line[id] = cur;
}
for (auto j : node[u]){
if (j.first == p) continue;
dep[j.first] = dep[u] + j.second;
dfs(j.first, u);
}
if (p){
line[id] = tmpP;
sz = tmp;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("A.inp", "r")){
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n;
cin >> n;
for (int i = 1; i < n; i++){
ll u, v, c;
cin >> u >> v >> c;
node[u].push_back({v, c});
node[v].push_back({u, c});
}
for (int i = 2; i <= n; i++){
cin >> a[i] >> b[i];
}
line[1] = {0, 0};
dfs(1, 0);
for (int i = 2; i <= n; i++) cout << dp[i] << " ";
}
/*
*/
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
73 | freopen("test.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
74 | freopen("test.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3308 KB |
Output is correct |
| 3 |
Correct |
54 ms |
11236 KB |
Output is correct |
| 4 |
Correct |
86 ms |
15200 KB |
Output is correct |
| 5 |
Correct |
104 ms |
18532 KB |
Output is correct |
| 6 |
Correct |
127 ms |
22372 KB |
Output is correct |
| 7 |
Correct |
80 ms |
12264 KB |
Output is correct |
| 8 |
Correct |
143 ms |
17760 KB |
Output is correct |
| 9 |
Correct |
141 ms |
19672 KB |
Output is correct |
| 10 |
Correct |
110 ms |
18136 KB |
Output is correct |
