#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int MAX = 100005;
typedef pair<int, int> pii;
vector<pii> g[MAX];
int dp[MAX][3];
int max(int a, int b, int c) { return max(max(a, b), c); }
void dfs(int u, int p=-1, int len=-1) {
for (pii i : g[u]) {
if (i.f == p) { continue; }
dfs(i.f, u, i.s);
}
int sum = 0;
vector<pii> unr; //unrooted
vector<pii> edgy; // edgy
for (pii i : g[u]) {
if (i.f == p) { continue; }
sum += max(dp[i.f][0], dp[i.f][1], dp[i.f][2]);
unr.push_back({max(dp[i.f][0], dp[i.f][1], dp[i.f][2]) - i.s - dp[i.f][2], i.f});
edgy.push_back({max(dp[i.f][0], dp[i.f][1], dp[i.f][2]) - i.s - max(dp[i.f][2], dp[i.f][0]), i.f});
}
sort(unr.begin(), unr.end());
sort(edgy.begin(), edgy.end());
for (int i=0; i<min(2, (int)unr.size()); i++) {
for (int j=0; j<min(2, (int)edgy.size()); j++) {
if (unr[i].s != edgy[j].s) {
dp[u][0] = max(dp[u][1], sum - unr[i].f - edgy[j].f);
}
}
}
if (p != -1) {
for (pii i : g[u]) {
if (i.f == p) { continue; }
dp[u][1] = max(dp[u][1], sum + len + i.s - max(dp[i.f][0], dp[i.f][1], dp[i.f][2]) + dp[i.f][0]);
}
}
dp[u][2] = sum;
// cout << u << " " << dp[u][0] << " " << dp[u][1] << " " << dp[u][2] << endl;
}
int main() {
int n; scanf("%d", &n);
for (int i=0; i<n-1; i++) {
int u, v, w; scanf("%d %d %d", &u, &v, &w);
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1);
printf("%d\n", max(dp[1][0], dp[1][1]));
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n; scanf("%d", &n);
~~~~~^~~~~~~~~~
beads.cpp:50:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v, w; scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
