#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <unordered_map>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef pair < int, int > pii;
typedef long long ll;
const int N = 6e5 + 500;
const ll INF = 1e15;
vector < int > g[N];
ll zbr[N], dp[3][N];
vector < pair < ll, int > > kand[N];
int n, jesam[N], vr[N], v[N];
ll f(int x, int fl, int brd){
if(dp[fl][brd] != -1)
return dp[fl][brd];
int lst = v[brd ^ 1];
//printf("pozvao x = %d fl = %d lst = %d\n", x, fl, lst);
//printf("brd = %d jesam = %d\n", brd, jesam[x]);
if(brd > 2 * n)
lst = v[brd];
if(jesam[x] == -1){
ll sm = 0;
for(int nxt : g[x]){
if(v[nxt] == lst) continue;
ll opt = max(f(v[nxt], 0, nxt), f(v[nxt], 1, nxt) + (ll)vr[nxt]);
sm += opt;
kand[x].PB({f(v[nxt], 2, nxt) + vr[nxt] - opt, v[nxt]});
}
kand[x].PB({-INF, -1});
kand[x].PB({-INF, -1});
//printf(" pripream teren s x = %d\n", x);
sort(kand[x].rbegin(), kand[x].rend());
jesam[x] = (x == lst ? -2 : brd ^ 1); zbr[x] = sm;
return dp[fl][brd] = sm + kand[x][0].X * (fl == 1);
}
if(jesam[x] >= 0 && v[jesam[x]] == lst){
return dp[fl][brd] = zbr[x] + kand[x][0].X * (fl == 1);
}
if(jesam[x] != -2){
ll opt = max(f(v[jesam[x]], 0, jesam[x]), f(v[jesam[x]], 1, jesam[x]) + vr[jesam[x]]);
zbr[x] += opt;
//printf(" ovdje je x = %d\n", x);
kand[x].PB({f(v[jesam[x]], 2, jesam[x]) + vr[jesam[x]] - opt, v[jesam[x]]});
sort(kand[x].rbegin(), kand[x].rend());
jesam[x] = -2;
}
ll sm = zbr[x] - (x == lst ? 0 : max(f(lst, 0, brd ^ 1), f(lst, 1, brd ^ 1) + vr[brd]));
//printf(" tu sam dosao %d\n", (int)kand[1].size());
ll dod = kand[x][0].X;
if(kand[x][0].Y == lst)
dod = kand[x][1].X;
//printf("zavrsio x = %d fl = %d lst = %d --> %lld + %lld\n", x, fl, lst, sm , dod * (fl == 1));
return dp[fl][x] = sm + dod * (fl == 1);
}
int main(){
memset(dp, -1, sizeof(dp));
memset(jesam , -1, sizeof(jesam));
scanf("%d", &n);
for(int i = 0;i + 1 < n;i++){
int x, y, z; scanf("%d%d%d", &x, &y, &z);
g[x].PB(2 * i), g[y].PB(2 * i + 1);
v[2 * i] = y, v[2 * i + 1] = x;
vr[2 * i] = z, vr[2 * i + 1] = z;
}
for(int i = 1;i <= n;i++)
v[2 * n + i] = i;
ll sol = 0;
for(int i = 1;i <= n;i++)
sol = max(sol, f(i, 0, 2 * n + i));
printf("%lld\n", sol);
return 0;
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
beads.cpp:73:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y, z; scanf("%d%d%d", &x, &y, &z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
45056 KB |
Output is correct |
| 2 |
Correct |
23 ms |
44928 KB |
Output is correct |
| 3 |
Correct |
26 ms |
45056 KB |
Output is correct |
| 4 |
Incorrect |
25 ms |
44928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
45056 KB |
Output is correct |
| 2 |
Correct |
23 ms |
44928 KB |
Output is correct |
| 3 |
Correct |
26 ms |
45056 KB |
Output is correct |
| 4 |
Incorrect |
25 ms |
44928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
45056 KB |
Output is correct |
| 2 |
Correct |
23 ms |
44928 KB |
Output is correct |
| 3 |
Correct |
26 ms |
45056 KB |
Output is correct |
| 4 |
Incorrect |
25 ms |
44928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
45056 KB |
Output is correct |
| 2 |
Correct |
23 ms |
44928 KB |
Output is correct |
| 3 |
Correct |
26 ms |
45056 KB |
Output is correct |
| 4 |
Incorrect |
25 ms |
44928 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
