#include<bits/stdc++.h>
#define oo 1000000000
#define maxn 200005
using namespace std;
typedef long long ll;
int n;
vector < pair < int, int > > g[maxn];
int dp[maxn][4];
void dfs(int u, int du) {
dp[u][0] = dp[u][1] = 0;
dp[u][2] = dp[u][3] = -oo;
for (auto i : g[u]) {
int v = i.first, w = i.second;
if (du == v) continue;
dfs(v, u);
if (u == 8) cerr << v << '\n';
int ret = max(dp[v][0], dp[v][1]);
int a = max(dp[u][0] + max(dp[v][1], dp[v][2] + w), dp[u][1] + dp[v][3] + w);
//if (u == 1) cerr << v << '\n';
a = max(a, max(dp[u][2] + ret, dp[u][3] + dp[v][1]) + w);
int b = dp[u][1] + max(dp[v][1], dp[v][2] + w);
int c = max(dp[u][2] + max(dp[v][2] + w, ret), dp[u][1] + dp[v][1] + w);
int d = max(dp[u][3] + max(dp[v][2] + w, ret), dp[u][1] + ret + w);
dp[u][0] = a;
dp[u][1] = b;
dp[u][2] = c;
dp[u][3] = d;
//if (u == 8) cerr << a << ' ' << b << ' ' << c << ' ' << d << '\n';
}
}
int main(){
#define TASK "ABC"
// freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v, c;
cin >> u >> v >> c;
g[u].push_back({v, c});
g[v].push_back({u, c});
}
int root = 1;
dfs(root, root);
//cerr << dp[8][1] << '\n';
cout << max(dp[root][0], dp[root][1]);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
8 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
9 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Incorrect |
7 ms |
4992 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
8 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
9 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Incorrect |
7 ms |
4992 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
8 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
9 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Incorrect |
7 ms |
4992 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
8 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
9 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Incorrect |
7 ms |
4992 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |