제출 #1032872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032872		vjudge1	구슬과 끈 (APIO14_beads)	C++17	0 / 100	1 ms	6764 KiB

beads

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e5+5, inf = 1e18;

int n, dp[2][N];
vector<pair<int, int>> adj[N];

void dfs(int x, int p, int w) {
  int sum1 = 0;
  int mx = -inf;
  int smx = -inf;
  for (auto& [y, z] : adj[x]) {
    if (y == p) continue;
    dfs(y, x, z);

    sum1 += dp[1][y];

    int nw = dp[0][y] + z - dp[1][y];
    if (nw >= mx) {
      smx = mx;
      mx = nw;
    }
    else if (nw > smx) {
      smx = nw;
    }
  }

  // no activo a nadie
  dp[0][x] = dp[1][x] = sum1;

  // activo a mi padre y a un hijo
  dp[1][x] = max(dp[1][x], sum1 + mx + w);

  // activo a dos hijos
  dp[0][x] = max(dp[0][x], sum1 + mx + smx);
  dp[1][x] = max(dp[1][x], sum1 + mx + smx);
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 0; i < n-1; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    x--; y--;

    adj[x].push_back(make_pair(y, z));
    adj[y].push_back(make_pair(x, z));
  }

  dfs(0, 0, 0);
  /*
  for (int i = 0; i < n; i++) {
    cerr << i << " " << dp[0][i] << " " << dp[1][i] << endl;
  }
  */

  cout << dp[0][0] << "\n";
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43