#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (ll i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;
vector<pair<ll, ll>> graph[200001];
ll dp1[200001], dp2[200001], dp3[200001];
void dfs(ll node, ll parent, ll edge) {
ll best = -1, second = -1;
ll best_val = ll_MIN, second_val = ll_MIN;
for (pair<ll, ll> i : graph[node]) {
if (i.first != parent) {
dfs(i.first, node, i.second);
dp1[node] += max(dp1[i.first], max(dp2[i.first], dp3[i.first]));
if (max(dp1[i.first], dp2[i.first]) + i.second - dp3[i.first] > best_val) {
second = best;
second_val = best_val;
best = i.first;
best_val = max(dp1[i.first], dp2[i.first]) + i.second - dp3[i.first];
} else if (max(dp1[i.first], dp2[i.first]) + i.second - dp3[i.first] > second_val) {
second = i.first;
second_val = max(dp1[i.first], dp2[i.first]) + i.second - dp3[i.first];
}
}
}
for (pair<ll, ll> i : graph[node]) {
if (i.first != parent) {
if (i.first == best) {
dp2[node] += max(dp1[i.first], dp2[i.first]) + i.second;
dp3[node] += max(dp1[i.first], dp2[i.first]) + i.second + edge;
} else if (i.first == second) {
dp2[node] += max(dp1[i.first], dp2[i.first]) + i.second;
dp3[node] += max(dp1[i.first], max(dp2[i.first], dp3[i.first]));
} else {
dp2[node] += max(dp1[i.first], max(dp2[i.first], dp3[i.first]));
dp3[node] += max(dp1[i.first], max(dp2[i.first], dp3[i.first]));
}
}
}
if (best == -1 || node == 1) dp3[node] = 0;
if (second == -1) dp2[node] = 0;
}
int main() {
iostream::sync_with_stdio(false);
cin.tie(0);
ll n;
cin >> n;
FOR(i, 1, n) {
ll a, b, c;
cin >> a >> b >> c;
graph[a].push_back({b, c});
graph[b].push_back({a, c});
}
dfs(1, 0, 0);
cout << max(dp1[1], dp2[1]) << '\n';
return 0;
}
Compilation message
beads.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
#pragma GCC Optimize("O3")
beads.cpp: In function 'void dfs(ll, ll, ll)':
beads.cpp:13:19: error: 'll_MIN' was not declared in this scope
ll best_val = ll_MIN, second_val = ll_MIN;
^~~~~~
beads.cpp:13:19: note: suggested alternative: 'FLT_MIN'
ll best_val = ll_MIN, second_val = ll_MIN;
^~~~~~
FLT_MIN
beads.cpp:23:17: error: 'second_val' was not declared in this scope
second_val = best_val;
^~~~~~~~~~
beads.cpp:23:17: note: suggested alternative: 'second'
second_val = best_val;
^~~~~~~~~~
second
beads.cpp:27:84: error: 'second_val' was not declared in this scope
} else if (max(dp1[i.first], dp2[i.first]) + i.second - dp3[i.first] > second_val) {
^~~~~~~~~~
beads.cpp:27:84: note: suggested alternative: 'second'
} else if (max(dp1[i.first], dp2[i.first]) + i.second - dp3[i.first] > second_val) {
^~~~~~~~~~
second
