///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> ii;
const int N = 2e5 + 10;
vector<int> adj[N], cost[N];
ll S[N], M[N], ans;
int n, pcost[N];
void calc(int u, int par) {
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i], c = cost[u][i];
if(v == par) continue;
pcost[v] = c; calc(v, u);
S[u] += max(S[v], M[v]);
}
for(int v : adj[u]) if(v - par) {
M[u] = max(M[u], S[u] - max(S[v], M[v]) + S[v] + pcost[u] + pcost[v]);
}
}
void solve(int u, int par) {
ans = max(ans, S[u]);
vector<ii> l = {{-1e18, 0}};
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i], c = cost[u][i];
l.push_back({-max(S[v], M[v]) + S[v] + c, v});
} sort(l.begin(), l.end(), greater<ii>());
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i], c = cost[u][i];
if(v == par) continue;
ll a = S[u], b = S[v], C = M[u], d = M[v];
S[u] -= max(S[v], M[v]);
M[u] = S[u] + c + (l[0].second == v ? l[1].first : l[0].first);
S[v] += max(S[u], M[u]);
solve(v, u);
S[u] = a, S[v] = b, M[u] = C, M[v] = d;
}
}
int main() {
int n; scanf("%d", &n);
for(int i = 1; i < n; i++) {
int u, v, c;
scanf("%d %d %d", &u, &v, &c);
adj[u].push_back(v);
adj[v].push_back(u);
cost[u].push_back(c);
cost[v].push_back(c);
}
calc(1, 0);
solve(1, 0);
printf("%lld\n", ans);
}
Compilation message
beads.cpp: In function 'void calc(int, int)':
beads.cpp:14:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
beads.cpp: In function 'void solve(int, int)':
beads.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
beads.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:45:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n; scanf("%d", &n);
~~~~~^~~~~~~~~~
beads.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Correct |
10 ms |
9728 KB |
Output is correct |
3 |
Correct |
9 ms |
9728 KB |
Output is correct |
4 |
Correct |
9 ms |
9728 KB |
Output is correct |
5 |
Correct |
10 ms |
9728 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
9 ms |
9728 KB |
Output is correct |
8 |
Correct |
9 ms |
9728 KB |
Output is correct |
9 |
Correct |
9 ms |
9728 KB |
Output is correct |
10 |
Correct |
9 ms |
9728 KB |
Output is correct |
11 |
Correct |
9 ms |
9728 KB |
Output is correct |
12 |
Correct |
9 ms |
9728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Correct |
10 ms |
9728 KB |
Output is correct |
3 |
Correct |
9 ms |
9728 KB |
Output is correct |
4 |
Correct |
9 ms |
9728 KB |
Output is correct |
5 |
Correct |
10 ms |
9728 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
9 ms |
9728 KB |
Output is correct |
8 |
Correct |
9 ms |
9728 KB |
Output is correct |
9 |
Correct |
9 ms |
9728 KB |
Output is correct |
10 |
Correct |
9 ms |
9728 KB |
Output is correct |
11 |
Correct |
9 ms |
9728 KB |
Output is correct |
12 |
Correct |
9 ms |
9728 KB |
Output is correct |
13 |
Correct |
9 ms |
9728 KB |
Output is correct |
14 |
Correct |
9 ms |
9728 KB |
Output is correct |
15 |
Correct |
9 ms |
9728 KB |
Output is correct |
16 |
Correct |
9 ms |
9728 KB |
Output is correct |
17 |
Correct |
10 ms |
9728 KB |
Output is correct |
18 |
Correct |
10 ms |
9728 KB |
Output is correct |
19 |
Correct |
9 ms |
9728 KB |
Output is correct |
20 |
Correct |
9 ms |
9728 KB |
Output is correct |
21 |
Correct |
10 ms |
9728 KB |
Output is correct |
22 |
Correct |
11 ms |
9700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Correct |
10 ms |
9728 KB |
Output is correct |
3 |
Correct |
9 ms |
9728 KB |
Output is correct |
4 |
Correct |
9 ms |
9728 KB |
Output is correct |
5 |
Correct |
10 ms |
9728 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
9 ms |
9728 KB |
Output is correct |
8 |
Correct |
9 ms |
9728 KB |
Output is correct |
9 |
Correct |
9 ms |
9728 KB |
Output is correct |
10 |
Correct |
9 ms |
9728 KB |
Output is correct |
11 |
Correct |
9 ms |
9728 KB |
Output is correct |
12 |
Correct |
9 ms |
9728 KB |
Output is correct |
13 |
Correct |
9 ms |
9728 KB |
Output is correct |
14 |
Correct |
9 ms |
9728 KB |
Output is correct |
15 |
Correct |
9 ms |
9728 KB |
Output is correct |
16 |
Correct |
9 ms |
9728 KB |
Output is correct |
17 |
Correct |
10 ms |
9728 KB |
Output is correct |
18 |
Correct |
10 ms |
9728 KB |
Output is correct |
19 |
Correct |
9 ms |
9728 KB |
Output is correct |
20 |
Correct |
9 ms |
9728 KB |
Output is correct |
21 |
Correct |
10 ms |
9728 KB |
Output is correct |
22 |
Correct |
11 ms |
9700 KB |
Output is correct |
23 |
Correct |
13 ms |
10112 KB |
Output is correct |
24 |
Correct |
14 ms |
10112 KB |
Output is correct |
25 |
Correct |
14 ms |
10112 KB |
Output is correct |
26 |
Correct |
20 ms |
10624 KB |
Output is correct |
27 |
Correct |
20 ms |
10624 KB |
Output is correct |
28 |
Correct |
20 ms |
11068 KB |
Output is correct |
29 |
Correct |
19 ms |
10752 KB |
Output is correct |
30 |
Correct |
19 ms |
10752 KB |
Output is correct |
31 |
Correct |
18 ms |
11520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9728 KB |
Output is correct |
2 |
Correct |
10 ms |
9728 KB |
Output is correct |
3 |
Correct |
9 ms |
9728 KB |
Output is correct |
4 |
Correct |
9 ms |
9728 KB |
Output is correct |
5 |
Correct |
10 ms |
9728 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
9 ms |
9728 KB |
Output is correct |
8 |
Correct |
9 ms |
9728 KB |
Output is correct |
9 |
Correct |
9 ms |
9728 KB |
Output is correct |
10 |
Correct |
9 ms |
9728 KB |
Output is correct |
11 |
Correct |
9 ms |
9728 KB |
Output is correct |
12 |
Correct |
9 ms |
9728 KB |
Output is correct |
13 |
Correct |
9 ms |
9728 KB |
Output is correct |
14 |
Correct |
9 ms |
9728 KB |
Output is correct |
15 |
Correct |
9 ms |
9728 KB |
Output is correct |
16 |
Correct |
9 ms |
9728 KB |
Output is correct |
17 |
Correct |
10 ms |
9728 KB |
Output is correct |
18 |
Correct |
10 ms |
9728 KB |
Output is correct |
19 |
Correct |
9 ms |
9728 KB |
Output is correct |
20 |
Correct |
9 ms |
9728 KB |
Output is correct |
21 |
Correct |
10 ms |
9728 KB |
Output is correct |
22 |
Correct |
11 ms |
9700 KB |
Output is correct |
23 |
Correct |
13 ms |
10112 KB |
Output is correct |
24 |
Correct |
14 ms |
10112 KB |
Output is correct |
25 |
Correct |
14 ms |
10112 KB |
Output is correct |
26 |
Correct |
20 ms |
10624 KB |
Output is correct |
27 |
Correct |
20 ms |
10624 KB |
Output is correct |
28 |
Correct |
20 ms |
11068 KB |
Output is correct |
29 |
Correct |
19 ms |
10752 KB |
Output is correct |
30 |
Correct |
19 ms |
10752 KB |
Output is correct |
31 |
Correct |
18 ms |
11520 KB |
Output is correct |
32 |
Correct |
81 ms |
14004 KB |
Output is correct |
33 |
Correct |
69 ms |
13920 KB |
Output is correct |
34 |
Correct |
69 ms |
13944 KB |
Output is correct |
35 |
Correct |
450 ms |
26780 KB |
Output is correct |
36 |
Correct |
455 ms |
26672 KB |
Output is correct |
37 |
Correct |
470 ms |
26756 KB |
Output is correct |
38 |
Correct |
350 ms |
31828 KB |
Output is correct |
39 |
Correct |
353 ms |
32156 KB |
Output is correct |
40 |
Correct |
351 ms |
31004 KB |
Output is correct |
41 |
Correct |
472 ms |
38024 KB |
Output is correct |