#include <stdio.h>
#include <vector>
using namespace std;
#define MAXN 100005
#define fi first
#define se second
typedef long long lint;
typedef pair<lint, int> pli;
typedef pair<int, int> pii;
int S[MAXN], V[MAXN];
vector<pii> ed[MAXN];
pii par[MAXN];
int dep[MAXN];
lint ans[MAXN], dp[MAXN];
pli link[17][MAXN];
vector<int> sta;
int main() {
int N;
int u, v, c;
int x, y;
lint dis;
scanf("%d", &N);
for(int i = 0; i < N - 1; i++) {
scanf("%d%d%d", &u, &v, &c);
ed[u].push_back(make_pair(c, v));
ed[v].push_back(make_pair(c, u));
}
for(int i = 2; i <= N; i++) scanf("%d%d", S + i, V + i);
par[1] = make_pair(0, 1);
for(int i = 0; i < 17; i++) link[i][1] = make_pair(0ll, 1);
dep[1] = 1;
sta.push_back(1);
while(!sta.empty()) {
//printf("dfs(%d)\n", x);
x = sta.back();
sta.pop_back();
if(x != 1) {
y = par[x].se;
dis = par[x].fi;
for(int i = 16; i >= 0; i--) if(dp[link[i][y].se] >= V[x]) {
dis += link[i][y].fi;
y = link[i][y].se;
}
if(dp[y] >= V[x]) {
dis += link[0][y].fi;
y = link[0][y].se;
}
ans[x] = ans[y] + dis * V[x] + S[x];
y = par[x].se;
dis = par[x].fi;
for(int i = 16; i >= 0; i--) if(ans[link[i][y].se] + (dis + link[i][y].fi) * (dp[link[i][y].se] + 1) > ans[x]) {
dis += link[i][y].fi;
y = link[i][y].se;
}
//printf("y = %d\n", y);
if(ans[y] + dis * (dp[y] + 1) > ans[x]) {
dis += link[0][y].fi;
y = link[0][y].se;
}
dp[x] = (ans[x] - ans[y]) / dis;
y = par[x].se;
dis = par[x].fi;
for(int i = 16; i >= 0; i--) if(dp[link[i][y].se] >= dp[x]) {
dis += link[i][y].fi;
y = link[i][y].se;
}
link[0][x] = dp[y] >= dp[x] ? make_pair(dis + link[0][y].fi, link[0][y].se) : make_pair(dis, y);
for(int i = 1; i < 17; i++)
link[i][x] = make_pair(link[i - 1][link[i - 1][x].se].fi + link[i - 1][x].fi, link[i - 1][link[i - 1][x].se].se);
}
//printf("x = %d, ans = %lld, dp = %lld, link = %d\n", x, ans[x], dp[x], link[0][x]);
for(auto a : ed[x]) if(a.se != par[x].se) {
par[a.se] = make_pair(a.fi, x);
dep[a.se] = dep[x] + 1;
sta.push_back(a.se);
}
}
for(int i = 2; i <= N; i++) printf("%lld ", ans[i]);
return 0;
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
harbingers.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &u, &v, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:34: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("%d%d", S + i, V + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
7 ms |
3704 KB |
Output is correct |
| 3 |
Correct |
99 ms |
16684 KB |
Output is correct |
| 4 |
Correct |
132 ms |
23672 KB |
Output is correct |
| 5 |
Correct |
166 ms |
30200 KB |
Output is correct |
| 6 |
Runtime error |
207 ms |
36668 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 7 |
Correct |
135 ms |
26872 KB |
Output is correct |
| 8 |
Runtime error |
278 ms |
37748 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 9 |
Runtime error |
266 ms |
37884 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 10 |
Runtime error |
240 ms |
37620 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
