제출 #255290

#제출 시각아이디문제언어결과실행 시간메모리
255290rama_pang구슬과 끈 (APIO14_beads)C++14
28 / 100
1089 ms5760 KiB
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const int MAXN = 2e5 + 5;
const lint INF = 1e18;

int N;
vector<pair<int, int>> adj[MAXN];

lint dp[MAXN][2]; // dp[u][do we use parent edge?]

void Dfs(int u, int p = -1) {
  dp[u][0] = dp[u][1] = 0;
  lint mx = -INF;
  for (auto e : adj[u]) if (e.first != p) {
    int v = e.first;
    int w = e.second;
    Dfs(v, u);
    dp[u][0] += max(dp[v][0], w + dp[v][1]);
    dp[u][1] += max(dp[v][0], w + dp[v][1]);
    mx = max(mx, dp[v][0] + w - max(dp[v][0], w + dp[v][1]));
  }
  dp[u][1] += mx;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N;
  for (int i = 0; i + 1 < N; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }

  lint ans = 0;
  for (int i = 0; i < N; i++) {
    Dfs(i);
    ans = max(ans, dp[i][0]);
  }
  cout << ans << "\n";
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...