#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e15 + 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][5], mark[maxn][5], 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
int ans = 0;
//dois filhos
//liga para 2 com aresta azul
ans = 0;
pair<int,int> mx2 = mp(-inf,-inf);
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,3,u)+w);
mx2.sc = max(mx2.sc, w + sol(v,0,u) - max(sol(v,1,u),sol(v,3,u)+w));
if(mx2.sc > mx2.fr) swap(mx2.sc,mx2.fr);
}
int ans2 = ans+mx2.fr+mx2.sc;
//liga para nenhum/todos ligam para ele
//ele pode ajudar exatamente um filho a ser sol(v,2,u)
ans = 0;
int mx0 = -inf;
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,3,u)+w);
mx0 = max(mx0, sol(v,2,u)+w - max(sol(v,1,u),sol(v,3,u)+w));
}
int ans0 = max(ans,ans+mx0);
//liga para 1 com aresta vermelha
int mx1 = -inf;
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,3,u)+w);
mx1 = max(mx1, sol(v,0,u) - max(sol(v,1,u),sol(v,3,u)+w));
}
int ans1 = ans+mx1;
// cout << u << " " << p << " = " << max({ans0,ans1,ans2}) << endl;
return dp[u][p] = max({ans0,ans1,ans2});
}
else if(p == 1) {
//p = 1, liga dele pro pai com red
int ans = 0;
//liga para nenhum/todos ligam para ele
//ele pode ajudar exatamente um filho a ser sol(v,2,u)
ans = 0;
int mx0 = -inf;
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,3,u)+w);
mx0 = max(mx0, sol(v,2,u)+w - max(sol(v,1,u),sol(v,3,u)+w));
}
int ans0 = max(ans,ans+mx0);
// cout << u << " " << p << " = " << ans0 << endl;
return dp[u][p] = ans0;
}
else if(p == 2) {
//o pai ja ligou para ele
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,3,u)+w);
mx = max(mx, w +sol(v,0,u) - max(sol(v,1,u),sol(v,3,u)+w));
}
// cout << u << " " << p << " = " << ans+mx << endl;
return dp[u][p] = ans+mx;
}
else if(p == 3) {
//o v especial vai ter que ligar pro pai
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,3,u)+w);
mx = max(mx, w + sol(v,1,u) - max(sol(v,1,u),sol(v,3,u)+w));
}
// cout << u << " " << p << " = " << ans+mx << endl;
return dp[u][p] = ans+mx;
}
return 0;
}
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:136:9: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
136 | int rt;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
3 ms |
5460 KB |
Output is correct |
3 |
Correct |
4 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 |
Correct |
3 ms |
5460 KB |
Output is correct |
7 |
Correct |
3 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
3 ms |
5460 KB |
Output is correct |
10 |
Correct |
3 ms |
5460 KB |
Output is correct |
11 |
Correct |
3 ms |
5460 KB |
Output is correct |
12 |
Correct |
3 ms |
5460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
3 ms |
5460 KB |
Output is correct |
3 |
Correct |
4 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 |
Correct |
3 ms |
5460 KB |
Output is correct |
7 |
Correct |
3 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
3 ms |
5460 KB |
Output is correct |
10 |
Correct |
3 ms |
5460 KB |
Output is correct |
11 |
Correct |
3 ms |
5460 KB |
Output is correct |
12 |
Correct |
3 ms |
5460 KB |
Output is correct |
13 |
Incorrect |
3 ms |
5460 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
3 ms |
5460 KB |
Output is correct |
3 |
Correct |
4 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 |
Correct |
3 ms |
5460 KB |
Output is correct |
7 |
Correct |
3 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
3 ms |
5460 KB |
Output is correct |
10 |
Correct |
3 ms |
5460 KB |
Output is correct |
11 |
Correct |
3 ms |
5460 KB |
Output is correct |
12 |
Correct |
3 ms |
5460 KB |
Output is correct |
13 |
Incorrect |
3 ms |
5460 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
3 ms |
5460 KB |
Output is correct |
3 |
Correct |
4 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 |
Correct |
3 ms |
5460 KB |
Output is correct |
7 |
Correct |
3 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
3 ms |
5460 KB |
Output is correct |
10 |
Correct |
3 ms |
5460 KB |
Output is correct |
11 |
Correct |
3 ms |
5460 KB |
Output is correct |
12 |
Correct |
3 ms |
5460 KB |
Output is correct |
13 |
Incorrect |
3 ms |
5460 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |