#include <bits/stdc++.h>
using namespace std;
constexpr int NMAX = 1e5 + 5;
typedef pair <int, int> PII;
typedef long long LL;
typedef pair <LL, LL> PLL;
constexpr LL INF = 1e16;
int N;
LL dist[NMAX];
int Dad[NMAX];
vector <PII> G[NMAX];
LL dp[NMAX];
LL V[NMAX], S[NMAX];
long double Intersect (PLL A, PLL B) {
return 1.0 * (A.second - B.second) / (B.first - A.first);
}
void Read () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i = 1; i < N; ++ i ) {
int x, y, c;
cin >> x >> y >> c;
G[x].push_back({y, c});
G[y].push_back({x, c});
}
for (int i = 2; i <= N; ++ i )
cin >> S[i] >> V[i];
dist[1] = 0;
dp[1] = 0;
}
void Dfs (int node, int dad = -1) {
Dad[node] = dad;
for (auto it : G[node]) {
int to = it.first;
int c = it.second;
if (to == dad) continue;
dist[to] = dist[node] + c;
Dfs(to, node);
}
}
void Solve (int Node, deque <PLL> D) {
int st = 0, dr = D.size()-1;
int ind = -1;
dp[Node] = dist[Node] * V[Node] + S[Node];
while (st <= dr) {
int mij = (st + dr) / 2;
pair <long double, long double> interval;
if (mij == 0) interval.first = -INF;
else interval.first = Intersect(D[mij-1], D[mij]);
if (mij == D.size()-1) interval.second = INF;
else interval.second = Intersect(D[mij], D[mij+1]);
if (interval.first > V[Node]) dr = mij - 1;
else if (interval.second < V[Node]) st = mij + 1;
else {
ind = mij;
break;
}
}
if (!D.empty())
dp[Node] = D[ind].first * V[Node] + D[ind].second + dist[Node] * V[Node] + S[Node];
PLL dreapta = {-dist[Node], dp[Node]};
while (D.size() >= 2 && Intersect(D[D.size()-2], D.back()) >= Intersect(D[D.size()-2], dreapta))
D.pop_back();
D.push_back(dreapta);
for (auto it : G[Node]) {
int to = it.first;
if (to == Dad[Node]) continue;
Solve(to, D);
}
}
int main () {
Read();
Dfs(1);
deque <PLL> emp;
Solve(1, emp);
for (int i = 2; i <= N; ++ i )
cout << dp[i] << " ";
return 0;
}
Compilation message
harbingers.cpp: In function 'void Solve(int, std::deque<std::pair<long long int, long long int> >)':
harbingers.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | if (mij == D.size()-1) interval.second = INF;
| ~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
5 ms |
4940 KB |
Output is correct |
3 |
Runtime error |
61 ms |
65540 KB |
Execution killed with signal 9 |
4 |
Runtime error |
82 ms |
65540 KB |
Execution killed with signal 9 |
5 |
Runtime error |
128 ms |
65540 KB |
Execution killed with signal 9 |
6 |
Runtime error |
129 ms |
65540 KB |
Execution killed with signal 9 |
7 |
Correct |
104 ms |
32120 KB |
Output is correct |
8 |
Runtime error |
108 ms |
65540 KB |
Execution killed with signal 9 |
9 |
Runtime error |
141 ms |
65540 KB |
Execution killed with signal 9 |
10 |
Runtime error |
98 ms |
65540 KB |
Execution killed with signal 9 |