#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
vector<pii> G[N];
int dp[N][2], W[N];
void dfs(int v, int p = -1){
int ttl = 0;
vector<int> ws;
for(pii pa : G[v]){
int i = pa.fi, w = pa.se;
if(i == p) continue;
W[i] = w;
dfs(i, v);
ws.push_back(w + dp[i][0] - dp[i][1]);
ttl += dp[i][1];
}
sort(ws.begin(), ws.end(), greater<>());
dp[v][0] = ttl;
if(p != -1 && ws.size() >= 1) dp[v][1] = ttl + W[v] + ws[0];
if(ws.size() >= 2) dp[v][0] = max(dp[v][0], ttl + ws[0] + ws[1]);
dp[v][1] = max(dp[v][0], dp[v][1]);
}
int32_t main(){
int n;
cin >> n;
for(int i = 0; i < n - 1; i++){
int u, v, we;
cin >> u >> v >> we;
G[u].pb({v, we});
G[v].pb({u, we});
}
dfs(1);
// for(int i = 1; i <= n; i++){
// cout << i << ": " << dp[i][0] << ' ' << dp[i][1] << endl;
// }
cout << max(dp[1][0], dp[1][1]) << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |