제출 #239705

#제출 시각아이디문제언어결과실행 시간메모리
239705neihcr7jBeads and wires (APIO14_beads)C++14
13 / 100
9 ms5120 KiB
#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;

   // if (u == 1) cerr << a << ' ' << b << ' ' << c << ' ' << d << '\n';
  }
}

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

  int root = 1;
  dfs(root, root);

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

  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...