#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
const int N = 1e4 + 5;
int n, dp[N][2], ans, g[N][2], cnt[N];
vector<ii> a[N], b[N];
vector<int> l[N], r[N], sax[2][N], cax[2][N];
void dfs(int u, int p) {
dp[u][0] = dp[u][1] = 0;
cnt[u] = 0;
for(int i = 0; i < a[u].size(); ++i) {
int v = a[u][i].first;
if(v == p) continue;
dfs(v, u);
cnt[u]++; b[u][cnt[u]] = a[u][i];
}
l[u][0] = 0;
for(int i = 1; i <= cnt[u]; ++i) {
int v = b[u][i].first, w = b[u][i].second;
l[u][i] = l[u][i - 1] + max(dp[v][1] + w, dp[v][0]);
}
r[u][cnt[u] + 1] = 0;
for(int i = cnt[u]; i >= 1; --i) {
int v = b[u][i].first, w = b[u][i].second;
r[u][i] = r[u][i + 1] + max(dp[v][1] + w, dp[v][0]);
}
dp[u][0] = l[u][cnt[u]];
for(int i = 1; i <= cnt[u]; ++i) {
int v = b[u][i].first, w = b[u][i].second;
dp[u][1] = max(dp[u][1], l[u][i - 1] + r[u][i + 1] + dp[v][0] + w);
}
if(a[u].size() == 1) dp[u][1] = -1e9;
}
void redfs(int u, int p) {
sax[1][u][0] = -1e9;
for(int i = 1; i <= cnt[u]; ++i) {
int v = b[u][i].first, w = b[u][i].second;
sax[0][u][i] = sax[0][u][i - 1] + max(dp[v][1] + w, dp[v][0]);
sax[1][u][i] = sax[0][u][i - 1] + w + dp[v][0];
sax[1][u][i] = max(sax[1][u][i], sax[1][u][i - 1] + max(dp[v][1] + w, dp[v][0]));
}
int W;
for(int i = 0; i < a[u].size(); ++i) if(a[u][i].first == p) W = a[u][i].second;
cax[0][u][cnt[u] + 1] = max(g[p][1] + W, g[p][0]);
cax[1][u][cnt[u] + 1] = W + g[p][0];
for(int i = cnt[u]; i >= 1; --i) {
int v = b[u][i].first, w = b[u][i].second;
cax[0][u][i] = cax[0][u][i + 1] + max(dp[v][1] + w, dp[v][0]);
cax[1][u][i] = cax[0][u][i + 1] + w + dp[v][0];
cax[1][u][i] = max(cax[1][u][i], cax[1][u][i + 1] + max(dp[v][1] + w, dp[v][0]));
}
ans = max(ans, sax[0][u][cnt[u] + 1]);
for(int i = 1; i <= cnt[u]; ++i) {
int v = b[u][i].first;
g[u][0] = sax[0][u][i - 1] + cax[0][u][i + 1];
g[u][1] = max(sax[1][u][i - 1] + cax[0][u][i + 1], sax[0][u][i - 1] + cax[1][u][i + 1]);
dfs(v, u);
}
}
int main() {
cin >> n;
for(int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
a[u].push_back(ii(v, w));
a[v].push_back(ii(u, w));
}
for(int i = 1; i <= n; ++i) l[i].assign(a[i].size() + 3, 0), r[i].assign(a[i].size() + 3, 0), b[i].assign(a[i].size() + 3, ii(0, 0)), sax[0][i].assign(a[i].size() + 3, 0), sax[1][i].assign(a[i].size() + 3, 0);
dfs(1, 1);
redfs(1, 1);
cout << ans;
}
Compilation message
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:15:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a[u].size(); ++i) {
~~^~~~~~~~~~~~~
beads.cpp: In function 'void redfs(int, int)':
beads.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a[u].size(); ++i) if(a[u][i].first == p) W = a[u][i].second;
~~^~~~~~~~~~~~~
beads.cpp:49:41: warning: 'W' may be used uninitialized in this function [-Wmaybe-uninitialized]
cax[0][u][cnt[u] + 1] = max(g[p][1] + W, g[p][0]);
~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4224 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4224 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4224 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
4224 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
