#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp>
#define X first
#define Y second
#define PB push_back
using namespace std;
using namespace __gnu_pbds;
typedef pair < int, int > pii;
typedef unsigned int ll;
const int N = 2e5 + 500;
const ll INF = 2e9;
vector < pii > v[N];
gp_hash_table < ll, ll > dp[3];
gp_hash_table < ll, ll > vr;
ll zbr[N];
vector < pair < ll, int > > kand[N];
int n, jesam[N];
ll f(int x, int fl, int lst){
if(dp[fl][x * N + lst] != 0)
return dp[fl][x * N + lst] - 1;
//printf("x = %d fl = %d lst = %d\n", x, fl, lst);
//char c; scanf("%c", &c);
if(!jesam[x]){
ll sm = 0;
for(pii nxt : v[x]){
if(nxt.X == lst) continue;
ll opt = max(f(nxt.X, 0, x), f(nxt.X, 1, x) + (ll)nxt.Y);
sm += opt;
kand[x].PB({f(nxt.X, 2, x) + nxt.Y - opt, nxt.X});
}
kand[x].PB({-INF, -1});
kand[x].PB({-INF, -1});
sort(kand[x].rbegin(), kand[x].rend());
jesam[x] = (x == lst ? n + 1 : lst); zbr[x] = sm;
return (dp[fl][x * N + lst] = sm + kand[x][0].X * (fl == 1) + 1) - 1;
}
if(jesam[x] == lst){
return (dp[fl][x * N + lst] = zbr[x] + kand[x][0].X * (fl == 1) + 1) - 1;
}
if(jesam[x] < n + 1){
ll opt = max(f(jesam[x], 0, x), f(jesam[x], 1, x) + vr[x * N + jesam[x]]);
zbr[x] += opt;
kand[x].PB({f(jesam[x], 2, x) + vr[x * N + jesam[x]] - opt, jesam[x]});
sort(kand[x].rbegin(), kand[x].rend());
jesam[x] = n + 1;
}
ll sm = zbr[x] - (x == lst ? 0 : max(f(lst, 0, x), f(lst, 1, x) + vr[x * N + lst]));
ll dod = kand[x][0].X;
if(kand[x][0].Y == lst)
dod = kand[x][1].X;
//printf("x = %d fl = %d lst = %d --> %lld + %lld\n", x, fl, lst, sm , dod * (fl == 1));
return (dp[fl][x * N + lst] = sm + dod * (fl == 1) + 1) - 1;
}
int main(){
scanf("%d", &n);
for(int i = 1;i < n;i++){
int x, y, z; scanf("%d%d%d", &x, &y, &z);
v[x].PB({y, z}), v[y].PB({x, z});
vr[x * N + y] = z, vr[y * N + x] = z;
}
ll sol = 0;
for(int i = 1;i <= n;i++)
sol = max(sol, f(i, 0, i));
printf("%d\n", sol);
return 0;
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
beads.cpp:71: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 |
Incorrect |
6 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
