#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>E[200100], L[200100];
int pL[201000], n, D[201000][4];
void DFS(int a, int pp){
int i, x, t1, t2, t3, t4, S = 0, S2 = 0, M1, M2, t, tt, M3, M4, x1, x2, x3, x4;
for (i = 0; i < E[a].size(); i++){
if (E[a][i] != pp){
pL[E[a][i]] = L[a][i];
DFS(E[a][i], a);
}
}
D[a][1] = D[a][2] = D[a][3] = -999999999;
if (!E[a].size())return;
M1 = M2 = M3 = M4 = -999999999;
x1 = x2 = x3 = x4 = -1;
for (i = 0; i < E[a].size(); i++){
x = E[a][i];
if (x == pp)continue;
t1 = D[x][0];
t2 = D[x][1] + pL[x];
t3 = D[x][2] + pL[x];
t4 = D[x][3];
tt = max(max(t1, t2), t4);
t = max(t3, tt);
S += t;
S2 += tt;
t1 = D[x][0] + pL[x] - tt;
t2 = D[x][3] + pL[x] - tt;
if (M1 < t1){ M2 = M1, x2 = x1; M1 = t1, x1 = i; }
else if (M2 < t1) M2 = t1, x2 = i;
if (M3 < t2){ M4 = M3, x4 = x3; M3 = t2, x3 = i; }
else if (M4 < t2) M4 = t2, x4 = i;
}
D[a][0] = S;
D[a][1] = S2 + M1;
D[a][2] = S2 + M3;
if (E[a].size() >= 2){
t1 = M1 + M2;
if (x1 == x3) t2 = max(M1 + M4, M2 + M3);
else t2 = M1 + M3;
D[a][3] = S2 + max(t1, t2);
}
}
int main(){
int i, a, b, d;
scanf("%d", &n);
for (i = 1; i < n; i++){
scanf("%d%d%d", &a, &b, &d);
E[a].push_back(b); E[b].push_back(a);
L[a].push_back(d); L[b].push_back(d);
}
DFS(1, 0);
printf("%d\n", max(D[1][0], D[1][3]));
}
Compilation message
beads.cpp: In function 'void DFS(int, int)':
beads.cpp:9:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < E[a].size(); i++){
~~^~~~~~~~~~~~~
beads.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < E[a].size(); i++){
~~^~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
beads.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &d);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9728 KB |
Output is correct |
2 |
Correct |
9 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 |
9 ms |
9728 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
10 ms |
9728 KB |
Output is correct |
8 |
Correct |
9 ms |
9728 KB |
Output is correct |
9 |
Correct |
11 ms |
9728 KB |
Output is correct |
10 |
Correct |
11 ms |
9728 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
10 ms |
9756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9728 KB |
Output is correct |
2 |
Correct |
9 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 |
9 ms |
9728 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
10 ms |
9728 KB |
Output is correct |
8 |
Correct |
9 ms |
9728 KB |
Output is correct |
9 |
Correct |
11 ms |
9728 KB |
Output is correct |
10 |
Correct |
11 ms |
9728 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
10 ms |
9756 KB |
Output is correct |
13 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9728 KB |
Output is correct |
2 |
Correct |
9 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 |
9 ms |
9728 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
10 ms |
9728 KB |
Output is correct |
8 |
Correct |
9 ms |
9728 KB |
Output is correct |
9 |
Correct |
11 ms |
9728 KB |
Output is correct |
10 |
Correct |
11 ms |
9728 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
10 ms |
9756 KB |
Output is correct |
13 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9728 KB |
Output is correct |
2 |
Correct |
9 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 |
9 ms |
9728 KB |
Output is correct |
6 |
Correct |
9 ms |
9728 KB |
Output is correct |
7 |
Correct |
10 ms |
9728 KB |
Output is correct |
8 |
Correct |
9 ms |
9728 KB |
Output is correct |
9 |
Correct |
11 ms |
9728 KB |
Output is correct |
10 |
Correct |
11 ms |
9728 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
10 ms |
9756 KB |
Output is correct |
13 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |