#include <bits/stdc++.h>
#define pii pair<int, int>
#define INF 1000000000000000000
using namespace std;
int N;
long long dp0[200005];//side
long long dp1[200005];//mid connect to 2 chlid (2 side or 1 side and 1 mid)
long long dp2[200005];//mid connect to 1 parent and 1 child (parent is side and child is mid)
long long dp3[200005];//mid connect to 1 parent and 1 child (parent can be side or mid, child is side)
vector<pii> adj[200005];
void DFS(int u, int p) {
int v, w;
long long bs = -INF, bs2 = -INF, bm = -INF, bm2 = -INF;
int id_bs = 0, id_bs2 = 0, id_bm = 0, id_bm2 = 0;
long long cur_side, cur_mid, best = 0, sum = 0, best_md = 0;
for(pii now : adj[u]) {
v = now.first, w = now.second;
if(v == p) continue;
DFS(v, u);
dp2[v] += w, dp3[v] += w;
best = max(dp0[v], dp2[v]);
sum += best;
best_md = max(best_md, max(dp1[v], dp3[v]) - best);
//best if choosen
cur_side = dp0[v] + w - best;
if(cur_side > bs) {
bs2 = bs, id_bs2 = id_bs;
bs = cur_side;
id_bs = v;
}else if(cur_side > bs2) {
bs2 = cur_side;
id_bs2 = v;
}
cur_mid = dp1[v] + w - best;
if(cur_mid > bm) {
bm2 = bm, id_bm2 = id_bm;
bm = cur_mid;
id_bm = v;
}else if(cur_mid > bm2) {
bm2 = cur_mid;
id_bm2 = v;
}
}
dp0[u] = sum;
//if mid connect 2 child
//1 side 1 mid
if(id_bs != id_bm) {
dp1[u] = sum + bs + bm;
}else {
dp1[u] = sum + max(bs + bm2, bs2 + bm);
}
dp1[u] = max(dp1[u], sum + bs + bs2);
dp1[u] = max(dp1[u], sum + best_md);
//if mid connect a parent and 1 red child
dp2[u] = sum + bs;
//if mid connect a red parent and a child
dp3[u] = sum + bm;
// cout << u << " " << dp0[u] << "\n";
}
int main() {
// freopen("inp.in", "r", stdin);
// freopen("out.out", "w", stdout);
scanf("%d", &N);
int u, v, w;
// cout << N << "\n";
for(int i = 1; i < N; i++) {
scanf("%d %d %d", &u, &v, &w);
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
DFS(1, 0);
cout << max(dp0[1], dp1[1]) << "\n";
cin >> N;
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/
Compilation message
beads.cpp: In function 'void DFS(int, int)':
beads.cpp:17:18: warning: variable 'id_bs2' set but not used [-Wunused-but-set-variable]
int id_bs = 0, id_bs2 = 0, id_bm = 0, id_bm2 = 0;
^~~~~~
beads.cpp:17:41: warning: variable 'id_bm2' set but not used [-Wunused-but-set-variable]
int id_bs = 0, id_bs2 = 0, id_bm = 0, id_bm2 = 0;
^~~~~~
beads.cpp: In function 'int main()':
beads.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
beads.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
Output is correct |
2 |
Correct |
3 ms |
4992 KB |
Output is correct |
3 |
Correct |
3 ms |
4992 KB |
Output is correct |
4 |
Correct |
3 ms |
4992 KB |
Output is correct |
5 |
Correct |
3 ms |
4992 KB |
Output is correct |
6 |
Correct |
3 ms |
4992 KB |
Output is correct |
7 |
Correct |
3 ms |
4992 KB |
Output is correct |
8 |
Correct |
3 ms |
4992 KB |
Output is correct |
9 |
Correct |
3 ms |
4992 KB |
Output is correct |
10 |
Correct |
4 ms |
4992 KB |
Output is correct |
11 |
Correct |
3 ms |
4992 KB |
Output is correct |
12 |
Correct |
3 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
Output is correct |
2 |
Correct |
3 ms |
4992 KB |
Output is correct |
3 |
Correct |
3 ms |
4992 KB |
Output is correct |
4 |
Correct |
3 ms |
4992 KB |
Output is correct |
5 |
Correct |
3 ms |
4992 KB |
Output is correct |
6 |
Correct |
3 ms |
4992 KB |
Output is correct |
7 |
Correct |
3 ms |
4992 KB |
Output is correct |
8 |
Correct |
3 ms |
4992 KB |
Output is correct |
9 |
Correct |
3 ms |
4992 KB |
Output is correct |
10 |
Correct |
4 ms |
4992 KB |
Output is correct |
11 |
Correct |
3 ms |
4992 KB |
Output is correct |
12 |
Correct |
3 ms |
4992 KB |
Output is correct |
13 |
Correct |
3 ms |
4992 KB |
Output is correct |
14 |
Correct |
3 ms |
5120 KB |
Output is correct |
15 |
Correct |
4 ms |
4992 KB |
Output is correct |
16 |
Correct |
4 ms |
4992 KB |
Output is correct |
17 |
Correct |
3 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
3 ms |
4992 KB |
Output is correct |
20 |
Correct |
3 ms |
4992 KB |
Output is correct |
21 |
Correct |
3 ms |
4992 KB |
Output is correct |
22 |
Correct |
3 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
Output is correct |
2 |
Correct |
3 ms |
4992 KB |
Output is correct |
3 |
Correct |
3 ms |
4992 KB |
Output is correct |
4 |
Correct |
3 ms |
4992 KB |
Output is correct |
5 |
Correct |
3 ms |
4992 KB |
Output is correct |
6 |
Correct |
3 ms |
4992 KB |
Output is correct |
7 |
Correct |
3 ms |
4992 KB |
Output is correct |
8 |
Correct |
3 ms |
4992 KB |
Output is correct |
9 |
Correct |
3 ms |
4992 KB |
Output is correct |
10 |
Correct |
4 ms |
4992 KB |
Output is correct |
11 |
Correct |
3 ms |
4992 KB |
Output is correct |
12 |
Correct |
3 ms |
4992 KB |
Output is correct |
13 |
Correct |
3 ms |
4992 KB |
Output is correct |
14 |
Correct |
3 ms |
5120 KB |
Output is correct |
15 |
Correct |
4 ms |
4992 KB |
Output is correct |
16 |
Correct |
4 ms |
4992 KB |
Output is correct |
17 |
Correct |
3 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
3 ms |
4992 KB |
Output is correct |
20 |
Correct |
3 ms |
4992 KB |
Output is correct |
21 |
Correct |
3 ms |
4992 KB |
Output is correct |
22 |
Correct |
3 ms |
4992 KB |
Output is correct |
23 |
Correct |
6 ms |
5504 KB |
Output is correct |
24 |
Correct |
6 ms |
5504 KB |
Output is correct |
25 |
Correct |
6 ms |
5504 KB |
Output is correct |
26 |
Correct |
9 ms |
5888 KB |
Output is correct |
27 |
Correct |
10 ms |
5888 KB |
Output is correct |
28 |
Correct |
8 ms |
5888 KB |
Output is correct |
29 |
Correct |
8 ms |
5888 KB |
Output is correct |
30 |
Correct |
8 ms |
5888 KB |
Output is correct |
31 |
Correct |
9 ms |
6400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
Output is correct |
2 |
Correct |
3 ms |
4992 KB |
Output is correct |
3 |
Correct |
3 ms |
4992 KB |
Output is correct |
4 |
Correct |
3 ms |
4992 KB |
Output is correct |
5 |
Correct |
3 ms |
4992 KB |
Output is correct |
6 |
Correct |
3 ms |
4992 KB |
Output is correct |
7 |
Correct |
3 ms |
4992 KB |
Output is correct |
8 |
Correct |
3 ms |
4992 KB |
Output is correct |
9 |
Correct |
3 ms |
4992 KB |
Output is correct |
10 |
Correct |
4 ms |
4992 KB |
Output is correct |
11 |
Correct |
3 ms |
4992 KB |
Output is correct |
12 |
Correct |
3 ms |
4992 KB |
Output is correct |
13 |
Correct |
3 ms |
4992 KB |
Output is correct |
14 |
Correct |
3 ms |
5120 KB |
Output is correct |
15 |
Correct |
4 ms |
4992 KB |
Output is correct |
16 |
Correct |
4 ms |
4992 KB |
Output is correct |
17 |
Correct |
3 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
3 ms |
4992 KB |
Output is correct |
20 |
Correct |
3 ms |
4992 KB |
Output is correct |
21 |
Correct |
3 ms |
4992 KB |
Output is correct |
22 |
Correct |
3 ms |
4992 KB |
Output is correct |
23 |
Correct |
6 ms |
5504 KB |
Output is correct |
24 |
Correct |
6 ms |
5504 KB |
Output is correct |
25 |
Correct |
6 ms |
5504 KB |
Output is correct |
26 |
Correct |
9 ms |
5888 KB |
Output is correct |
27 |
Correct |
10 ms |
5888 KB |
Output is correct |
28 |
Correct |
8 ms |
5888 KB |
Output is correct |
29 |
Correct |
8 ms |
5888 KB |
Output is correct |
30 |
Correct |
8 ms |
5888 KB |
Output is correct |
31 |
Correct |
9 ms |
6400 KB |
Output is correct |
32 |
Correct |
35 ms |
9208 KB |
Output is correct |
33 |
Correct |
36 ms |
9208 KB |
Output is correct |
34 |
Correct |
35 ms |
9208 KB |
Output is correct |
35 |
Correct |
210 ms |
22392 KB |
Output is correct |
36 |
Correct |
201 ms |
22264 KB |
Output is correct |
37 |
Correct |
252 ms |
22264 KB |
Output is correct |
38 |
Correct |
151 ms |
22764 KB |
Output is correct |
39 |
Correct |
176 ms |
22616 KB |
Output is correct |
40 |
Correct |
212 ms |
22624 KB |
Output is correct |
41 |
Correct |
184 ms |
27628 KB |
Output is correct |