#include<stdio.h>
#include<algorithm>
#define MAXN 200010
#define MAXM 200010
using namespace std;
int n;
int nxt[MAXM*2], st[MAXN], en[MAXM*2], wei[MAXM*2];
int dyn[MAXN][2];
void dfs(int here, int p, int uew) {
int i, sum = 0, m1 = -2e9, m2 = -2e9;
for (i=st[here];i!=-1;i=nxt[i]) {
int there = en[i];
if (there==p) continue;
dfs(there,here,wei[i]);
sum += dyn[there][1];
int val = dyn[there][0]-dyn[there][1]+wei[i];
if (m1<val) {m2=m1;m1=val;}
else if (m2<val) m2=val;
}
if (m2==-2e9) dyn[here][0] = sum;
else dyn[here][0] = max(sum,sum+m1+m2);
if (m1==-2e9) dyn[here][1] = dyn[here][0];
else dyn[here][1] = max(dyn[here][0],sum+m1+uew);
}
void process() {
dfs(0,-1,0);
printf("%d\n",dyn[0][0]);
}
int ptr = 0;
void add_edge(int u, int v, int w) {
nxt[ptr] = st[u];
wei[ptr] = w;
en[ptr] = v;
st[u] = ptr++;
nxt[ptr] = st[v];
wei[ptr] = w;
en[ptr] = u;
st[v] = ptr++;
}
void input() {
int i;
scanf("%d",&n);
for (i=0;i<n;i++) st[i] = -1;
for (i=0;i<n-1;i++) {
int a, b, w;
scanf("%d %d %d",&a,&b,&w);
add_edge(--a,--b,w);
}
}
int main() {
input();
process();
return 0;
}
Compilation message
beads.cpp: In function 'void input()':
beads.cpp:47: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,&w);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
300 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
300 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Incorrect |
2 ms |
300 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
300 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
300 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Incorrect |
2 ms |
300 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
300 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
300 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Incorrect |
2 ms |
300 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
300 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
300 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Incorrect |
2 ms |
300 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |