#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
int N;
vector<pii> adj[101010];
LL A[101010], B[101010], ans[101010], D[101010];
int W[101010], H[101010], P[101010];
struct CHT{
vector<pii> L;
void push(pii l){
int t = L.size()-1;
while(t > 0 && (L[t].second-l.second)*(L[t].first-L[t-1].first) < (L[t-1].second-L[t].second)*(l.first-L[t].first)) L.pop_back(), t--;
L.push_back(l);
}
LL read(LL x){
if (L.size() == 1) return 0;
int l=1, r=L.size()-1, ret=0;
while (l <= r){
int mid = (l+r)/2;
if (L[mid-1].second-L[mid].second < x*(L[mid].first-L[mid-1].first)) ret=mid, l = mid+1;
else r = mid-1;
}
return L[ret].first * x + L[ret].second;
}
} CH[101010];
int dfs(int u, int p){
W[u] = 1;
for (pii v : adj[u]){
if (v.first == p) continue;
D[v.first] = D[u] + v.second;
W[u] += dfs(v.first, u);
}
sort(adj[u].begin(), adj[u].end(), [&](pii a, pii b){
if (a.first == p) return false;
if (b.first == p) return true;
return W[a.first] < W[b.first];
});
if (u != 1) adj[u].pop_back();
return W[u];
}
void HLD(int u, int p, int r){
H[u] = r, P[u] = p;
for (int i=0; i<(int)adj[u].size()-1; i++) HLD(adj[u][i].first, u, adj[u][i].first);
if (!adj[u].empty()) HLD(adj[u].back().first, u, r);
}
void solve(int u){
if (u != 1){
ans[u] = 1ll << 61;
for (int a=u; a!=0; a=P[H[a]]) if (H[a] != u) ans[u] = min(ans[u], A[u]*D[u] + B[u] - CH[H[a]].read(A[u]));
}
CH[H[u]].push(pii(D[u], -ans[u]));
for (pii v : adj[u]) solve(v.first);
}
int main(){
scanf("%d", &N);
for (int i=1; i<N; i++){
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
adj[u].push_back(pii(v, w));
adj[v].push_back(pii(u, w));
}
for (int i=2; i<=N; i++) scanf("%lld %lld", &B[i], &A[i]);
dfs(1, 0);
HLD(1, 0, 1);
solve(1);
for (int i=2; i<=N; i++) printf("%lld ", ans[i]);
return 0;
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
harbingers.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:71:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i=2; i<=N; i++) scanf("%lld %lld", &B[i], &A[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
2 |
Correct |
9 ms |
5624 KB |
Output is correct |
3 |
Correct |
70 ms |
14200 KB |
Output is correct |
4 |
Correct |
109 ms |
18548 KB |
Output is correct |
5 |
Correct |
143 ms |
22264 KB |
Output is correct |
6 |
Correct |
205 ms |
26400 KB |
Output is correct |
7 |
Incorrect |
99 ms |
15224 KB |
Output isn't correct |
8 |
Incorrect |
251 ms |
22268 KB |
Output isn't correct |
9 |
Incorrect |
195 ms |
24036 KB |
Output isn't correct |
10 |
Incorrect |
157 ms |
23024 KB |
Output isn't correct |