#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
long long D[100009];
struct line {
int A, B;
long long get(int x) { return 1LL*A*x + D[B]; }
};
struct node {
int lc, rc;
line l;
};
const int iNF = 1e9;
const long long INF = 5LL * 1e18;
node EMP = {-1, -1, {0, 100001}};
vector<int> VS;
node T[900009]; int to, rs, re, rm, m;
void add(node pi, node &ni, int s, int e, line L) {
// printf("add: (%d, %d)\n", L.A, L.B);
ni = pi;
m = s+e >> 1;
rs = VS[s-1], re = VS[e-1], rm = VS[m-1];
if(L.get(rs) >= ni.l.get(rs) && L.get(re) >= ni.l.get(re)) return;
if(L.get(rs) <= ni.l.get(rs) && L.get(re) <= ni.l.get(re)) {ni.l = L; return;}
if(L.get(rs) > ni.l.get(rs)) swap(L, ni.l);
if(L.get(rm) < ni.l.get(rm)) {
swap(L, ni.l);
ni.rc = to; T[to++] = EMP;
if(pi.rc == -1) add(EMP, T[ni.rc], m, e, L);
else add(T[pi.rc], T[ni.rc], m, e, L);
}
else {
ni.lc = to; T[to++] = EMP;
if(pi.lc == -1) add(EMP, T[ni.lc], s, m, L);
else add(T[pi.lc], T[ni.lc], s, m, L);
}
}
long long get(node id, int s, int e, int x) {
// printf("get: (%lld, %lld)\n", id.l.A, id.l.B);
if(x < s || e < x) return INF;
m = s+e >> 1;
long long ret = id.l.get(VS[x-1]);
if(id.lc != -1) ret = min(ret, get(T[id.lc], s, m, x));
if(id.rc != -1) ret = min(ret, get(T[id.rc], m, e, x));
return ret;
}
int S[100009], V[100009], K;
vector<pii> adj[100009];
int getx(int x) {
return lower_bound(VS.begin(), VS.end(), x) - VS.begin() + 1;
}
void dfs(int x, int p, int de) {
if(x != 1) D[x] = get(T[S[p]], 1, K, getx(V[x])) + 1LL*de*V[x] + S[x];
S[x] = to; T[to++] = EMP;
add(T[S[p]], T[S[x]], 1, K, {-de, x});
for(auto& it: adj[x]) if(it.first != p) dfs(it.first, x, de + it.second);
to = S[x];
}
int main() {
D[100001] = INF;
int N; scanf("%d",&N);
for(int i=0; i<N-1; i++) {
int u, v, w; scanf("%d%d%d",&u,&v,&w);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for(int i=2; i<=N; i++) {
scanf("%d%d",&S[i],&V[i]);
VS.push_back(V[i]);
}
sort(VS.begin(), VS.end()); VS.resize(unique(VS.begin(), VS.end()) - VS.begin());
K = VS.size();
T[to++] = EMP;
dfs(1, 0, 0);
for(int i=2; i<=N; i++) printf("%lld ", D[i]);
return 0;
}
Compilation message
harbingers.cpp: In function 'void add(node, node&, int, int, line)':
harbingers.cpp:27:7: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
m = s+e >> 1;
~^~
harbingers.cpp: In function 'long long int get(node, int, int, int)':
harbingers.cpp:47:7: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
m = s+e >> 1;
~^~
harbingers.cpp: In function 'int main()':
harbingers.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int N; scanf("%d",&N);
~~~~~^~~~~~~~~
harbingers.cpp:73:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v, w; scanf("%d%d%d",&u,&v,&w);
~~~~~^~~~~~~~~~~~~~~~~~~
harbingers.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&S[i],&V[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2684 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3064 KB |
Output is correct |
| 3 |
Correct |
79 ms |
13560 KB |
Output is correct |
| 4 |
Correct |
121 ms |
23028 KB |
Output is correct |
| 5 |
Correct |
189 ms |
16144 KB |
Output is correct |
| 6 |
Correct |
164 ms |
16928 KB |
Output is correct |
| 7 |
Correct |
107 ms |
10020 KB |
Output is correct |
| 8 |
Correct |
211 ms |
21268 KB |
Output is correct |
| 9 |
Correct |
269 ms |
27024 KB |
Output is correct |
| 10 |
Correct |
185 ms |
24284 KB |
Output is correct |
