#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e6 + 100;
const int mod = (int)1e9+7;
int n;
vector<pair<int, int> > g[maxn];
vector< ll > pref[maxn];
vector< ll > suff[maxn];
vector< ll > pref2[maxn];
vector< ll > suff2[maxn];
ll dp[maxn][2];
void dfs(int v, int p) {
ll sum = 0;
ll sum1 = -1<<50;
for(auto[to, w]: g[v]) {
pref[v].push_back(sum);
pref2[v].push_back(sum1);
if(to == p) {
continue;
}
dfs(to, v);
sum1 = max(sum1 + max(dp[to][0], dp[to][1] + w), sum + dp[to][0] + w);
sum += max(dp[to][0], dp[to][1] + w);
}
dp[v][0] = sum;
sum = 0;
dp[v][1] = -(1ll<<50);
sum1 = -(1ll<<50);
for(int i = (int)g[v].size() - 1; i >= 0; i--) {
int to = g[v][i].first;
suff[v].push_back(sum);
suff2[v].push_back(sum1);
int w = g[v][i].second;
if(to == p) continue;
sum1 = max(sum1 + max(dp[to][0], dp[to][1] + w), sum + dp[to][0] + w);
dp[v][1] = max(dp[v][1], sum + pref[v][i] + g[v][i].second + dp[to][0]);
sum += max(dp[to][0], dp[to][1] + g[v][i].second);
}
reverse(suff[v].begin(), suff[v].end());
reverse(suff2[v].begin(), suff2[v].end());
}
ll ans;
void calc(int v, int p, ll dp0, ll dp1) {
ans = max(ans, dp[v][0] + dp0);
ll sum1 = dp0;
ll sum2 = dp1;
for(int i = 0;i < g[v].size(); i++) {
int to = g[v][i].first;
int w = g[v][i].second;
if(to == p) continue;
ans = max(ans, sum2 + w + suff[v][i] + dp[to][0]);
ll up0 = max(dp0, dp1+w) + pref[v][i] + suff[v][i];
up0 = max(dp0 + pref2[v][i]+suff[v][i] + w, up0);
up0 = max(dp0 + pref[v][i]+suff2[v][i] + w, up0);
calc(to, v, up0, pref[v][i] + suff[v][i] + dp0 + w);
sum2 = max(sum2 + max(dp[to][0], dp[to][1] + w), sum1 + dp[to][0] + w);
sum1 += max(dp[to][0], dp[to][1] + w);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 0);
calc(1, 0, 0, -(1ll<<50));
cout << ans << "\n";
}
Compilation message
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:18:17: warning: left shift count >= width of type [-Wshift-count-overflow]
18 | ll sum1 = -1<<50;
| ~~^~~~
beads.cpp: In function 'void calc(int, int, ll, ll)':
beads.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i = 0;i < g[v].size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
117724 KB |
Output is correct |
| 2 |
Incorrect |
55 ms |
117704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
117724 KB |
Output is correct |
| 2 |
Incorrect |
55 ms |
117704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
117724 KB |
Output is correct |
| 2 |
Incorrect |
55 ms |
117704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
117724 KB |
Output is correct |
| 2 |
Incorrect |
55 ms |
117704 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
