#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = 100'005;
vector<pair<int, ll>> adj[MAXN];
ll prep[MAXN], tim[MAXN], dp[MAXN], dist = 0;
struct line{
ll m, c;
ll eval(ll x){
return m * x + c;
}
};
line dq[MAXN]; int dqsz = 0;
ld poi(line a, line b) {
return (ld)(a.c - b.c) / (b.m - a.m);
}
ll query(ll x){
if (dqsz == 0) return 0;
int l = 0, r = dqsz - 2, ans = dqsz - 1;
while (l <= r){
int m = (l + r) >> 1;
if (dq[m].eval(x) <= dq[m + 1].eval(x)){
ans = m;
r = m - 1;
}
else l = m + 1;
}
return dq[ans].eval(x);
}
void dfs(int x, int par){
if (x == 1) dp[x] = 0;
else dp[x] = prep[x] + dist * tim[x] + query(tim[x]);
line a = {-dist, dp[x]};
int orisz = dqsz;
while (dqsz >= 2 && poi(dq[dqsz - 1], a) <= poi(dq[dqsz - 1], dq[dqsz - 2])) dqsz--;
line rln = dq[dqsz];
dq[dqsz] = a; dqsz++;
for (auto nxt : adj[x]){
int nn = nxt.first; ll nd = nxt.second;
if (nn == par) continue;
dist += nd;
dfs(nn, x);
dist -= nd;
}
dq[dqsz - 1] = rln;
dqsz = orisz;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int nodes; cin >> nodes;
for (int i = 1; i < nodes; i++){
int a, b; ll d; cin >> a >> b >> d;
adj[a].push_back({b, d});
adj[b].push_back({a, d});
}
for (int i = 2; i <= nodes; i++) cin >> prep[i] >> tim[i];
dfs(1, -1);
for (int i = 2; i <= nodes; i++) cout << dp[i] << ' ';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3156 KB |
Output is correct |
| 3 |
Correct |
45 ms |
10144 KB |
Output is correct |
| 4 |
Correct |
56 ms |
13892 KB |
Output is correct |
| 5 |
Correct |
75 ms |
17048 KB |
Output is correct |
| 6 |
Correct |
88 ms |
20396 KB |
Output is correct |
| 7 |
Correct |
64 ms |
10880 KB |
Output is correct |
| 8 |
Execution timed out |
1096 ms |
14532 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1067 ms |
16336 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1077 ms |
15252 KB |
Time limit exceeded |
