제출 #239685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239685		neihcr7j	구슬과 끈 (APIO14_beads)	C++14	0 / 100	7 ms	5120 KiB

beads

#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);

    int ret = max(dp[v][0], dp[v][1]);

    int a = max(dp[u][0] + max(ret, dp[v][2] + w), dp[u][1] + dp[v][3] + w);
    a = max(a, max(dp[u][2] + ret, dp[u][3] + dp[v][1] + w));

    int b = dp[u][1] + max(ret, 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;
  }
}

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});
  }

  dfs(1, 1);

  cout << max(dp[1][0], dp[1][1]);

  return 0;
}

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