Submission #41613

#	Time	Username	Problem	Language	Result	Execution time	Memory
41613		funcsr	구슬과 끈 (APIO14_beads)	C++14	28 / 100	1071 ms	5476 KiB

beads

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919

int N;
vector<P> G[200000];
int dp[200000][2];
//void update(int x, int p, int src) {
//}
void dfs(int x, int p) {
  dp[x][0] = 0;
  dp[x][1] = -INF;
  for (P pp : G[x]) if (pp._1 != p) {
    int t = pp._1, len = pp._2;
    dfs(t, x);
    int v = max(dp[t][0], dp[t][1]+len);
    dp[x][0] += v;
    dp[x][1] += v;
    dp[x][1] = max(dp[x][1], dp[x][0]-v + dp[t][0]+len);
  }
}

int main() {
  cin >> N;
  rep(i, N-1) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    G[a].pb(P(b, c));
    G[b].pb(P(a, c));
  }
  //dfs(0, -1);

  int m = 0;
  rep(i, N) {
    dfs(i, -1);
    m = max(m, dp[i][0]);
  }
  cout << m << "\n";
  return 0;
}

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