| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 552165 | QwertyPi | 구슬과 끈 (APIO14_beads) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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]){
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;
}