#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define F first
#define S second
#define int long long
using namespace std;
const int N = 1e5 + 5, MOD = 1e9 + 7;
vector<pair<int, int> > g[N];
int n, par[N], dis[N], dp[N], s[N], d[N];
struct Line{
int m, c;
int val(int x){
return m*x + c;
}
};
vector<Line> hulls;
int cur_hullsize;
bool check(Line a, Line b, Line cc){
int x = (b.c - a.c);
x = x * (a.m - cc.m);
int y = (cc.c - a.c);
y = y * (a.m - b.m);
if(x > y)
return true;
return false;
}
int pos(int mm, int cc){
Line cur;
cur.m = mm;
cur.c = cc;
if(cur_hullsize < 2)
return cur_hullsize;
int low = 1, high = cur_hullsize - 1, ans = cur_hullsize;
while(low <= high){
int mid = (low + high) / 2;
if(check(hulls[mid - 1], hulls[mid], cur)){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
int get(int x){
if(hulls.empty())
return (long long) LLONG_MAX;
int low = 0, high = (int) cur_hullsize - 2, ans = (int) cur_hullsize - 1;
while(low <= high){
int mid = (low + high) / 2;
if(hulls[mid].val(x) <= hulls[mid + 1].val(x)){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return hulls[ans].val(x);
}
void dfs(int node, int p, int sum){
dis[node] = sum;
par[node] = p;
for(auto k : g[node]){
if(k.F == p) continue;
dfs(k.F, node, sum + k.S);
}
}
/*
we want to find the position in the convex hull where the current line will go
we will replace that position with the current line
we will change it back once I go up from that node
*/
void dfs1(int node){
int mn = s[node] + dis[node] * d[node];
int x = get(d[node]);
if(x != LLONG_MAX)
mn = min(mn, x + s[node] + dis[node] * d[node]);
dp[node] = mn;
int cur, here = cur_hullsize;
Line pre;
pre.m = 1;
if(node != 1){
cur = cur_hullsize = pos(-dis[node], dp[node]);
Line neww;
neww.m = -dis[node];
neww.c = dp[node];
if(cur == hulls.size())
hulls.pb(neww);
else{
pre = hulls[cur];
hulls[cur] = neww;
}
cur_hullsize++;
}
for(auto k : g[node]){
if(k.F == par[node])
continue;
dfs1(k.F);
}
if(node != 1){
cur_hullsize = here;
if(pre.m == 1)
hulls.pop_back();
else
hulls[cur] = pre;
}
}
void solve(){
cin >> n;
for(int i = 1; i < n; ++i){
int u, v, c;
cin >> u >> v >> c;
g[u].pb({v, c});
g[v].pb({u, c});
}
for(int i = 1; i < n; ++i)
cin >> s[i + 1] >> d[i + 1];
dfs(1, 0, 0);
dfs1(1);
for(int i = 2; i <= n; ++i)
cout << dp[i] << " ";
}
int32_t main(){
fast;
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
Compilation message
harbingers.cpp: In function 'void dfs1(long long int)':
harbingers.cpp:96:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | if(cur == hulls.size())
| ~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3156 KB |
Output is correct |
| 3 |
Incorrect |
49 ms |
11344 KB |
Output isn't correct |
| 4 |
Correct |
74 ms |
15976 KB |
Output is correct |
| 5 |
Correct |
77 ms |
19508 KB |
Output is correct |
| 6 |
Correct |
111 ms |
23528 KB |
Output is correct |
| 7 |
Correct |
49 ms |
12296 KB |
Output is correct |
| 8 |
Incorrect |
119 ms |
18200 KB |
Output isn't correct |
| 9 |
Correct |
101 ms |
20224 KB |
Output is correct |
| 10 |
Correct |
86 ms |
18888 KB |
Output is correct |
