#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 220000
int n, dp[maxn][4], mark[maxn][4], a[maxn], b[maxn], c[maxn];
vector<pair<int,int>> g[maxn];
int sol(int u, int p, int ant) {
if(mark[u][p]) return dp[u][p];
mark[u][p] = 1;
if(p == 0) {
//o pai liga para ele, entao pode ligar para 2 com
//aresta azul, para 1 com aresta vermelha ou para nenhum
//liga para nenhum/todos ligam para ele
int ans0 = 0;
for(auto V : g[u]) {
int v = V.fr;
int w = V.sc;
if(v == ant) continue;
ans0+= max(sol(v,1,u),sol(v,2,u)+w);
}
//liga para 1 com aresta vermelha
int mx1 = -inf;
for(auto V : g[u]) {
int v = V.fr;
int w = V.sc;
if(v == ant) continue;
mx1 = max(mx1, sol(v,0,u) - max(sol(v,1,u),sol(v,2,u)+w));
}
int ans1 = ans0+mx1;
//liga para 2 com aresta azul
pair<int,int> mx2 = mp(-inf,-inf);
for(auto V : g[u]) {
int v = V.fr;
int w = V.sc;
if(v == ant) continue;
mx2.sc = max(mx2.sc, w + sol(v,0,u) - max(sol(v,1,u),sol(v,2,u)+w));
if(mx2.sc > mx2.fr) swap(mx2.sc,mx2.fr);
}
int ans2 = ans0 + mx2.fr + mx2.sc;
return dp[u][p] = max({ans0,ans1,ans2});
}
else if(p == 1) {
//p = 1, liga dele pro pai com red
int ans = 0;
//todos tem que ligar deles para o u
for(auto V : g[u]) {
int v = V.fr;
int w = V.sc;
if(v == ant) continue;
ans+= max(sol(v,1,u),sol(v,2,u)+w);
}
return dp[u][p] = ans;
}
else {
int mx = -inf;
int ans = 0;
for(auto V : g[u]) {
int v = V.fr;
int w = V.sc;
if(v == ant) continue;
ans+= max(sol(v,1,u),sol(v,2,u)+w);
mx = max(mx, w +sol(v,0,u) - max(sol(v,1,u),sol(v,2,u)+w));
}
return dp[u][p] = ans+mx;
}
}
void solve() {
cin >> n;
for(int i = 1; i < n; i++) {
cin >> a[i] >> b[i] >> c[i];
g[a[i]].pb(mp(b[i],c[i]));
g[b[i]].pb(mp(a[i],c[i]));
}
int rt;
for(int i = 1; i <= n; i++) {
if(g[i].size() == 1) {
rt = i;
break;
}
}
cout << sol(rt,0,0) << endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) solve();
}
Compilation message
beads.cpp: In function 'void solve()':
beads.cpp:103:9: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
103 | int rt;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5460 KB |
Output is correct |
2 |
Correct |
3 ms |
5460 KB |
Output is correct |
3 |
Correct |
3 ms |
5460 KB |
Output is correct |
4 |
Correct |
3 ms |
5460 KB |
Output is correct |
5 |
Correct |
3 ms |
5460 KB |
Output is correct |
6 |
Incorrect |
3 ms |
5460 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5460 KB |
Output is correct |
2 |
Correct |
3 ms |
5460 KB |
Output is correct |
3 |
Correct |
3 ms |
5460 KB |
Output is correct |
4 |
Correct |
3 ms |
5460 KB |
Output is correct |
5 |
Correct |
3 ms |
5460 KB |
Output is correct |
6 |
Incorrect |
3 ms |
5460 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5460 KB |
Output is correct |
2 |
Correct |
3 ms |
5460 KB |
Output is correct |
3 |
Correct |
3 ms |
5460 KB |
Output is correct |
4 |
Correct |
3 ms |
5460 KB |
Output is correct |
5 |
Correct |
3 ms |
5460 KB |
Output is correct |
6 |
Incorrect |
3 ms |
5460 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5460 KB |
Output is correct |
2 |
Correct |
3 ms |
5460 KB |
Output is correct |
3 |
Correct |
3 ms |
5460 KB |
Output is correct |
4 |
Correct |
3 ms |
5460 KB |
Output is correct |
5 |
Correct |
3 ms |
5460 KB |
Output is correct |
6 |
Incorrect |
3 ms |
5460 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |