제출 #1364747

#제출 시각아이디문제언어결과실행 시간메모리
1364747jump구슬과 끈 (APIO14_beads)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
#define int long long
const int INF = 1e9;
int n;
std::vector<std::pair<int,int>> adj[100000];
int dp[100000][2];
int dfs(int curr,int par){
  int mx1=-1,mx2=-1;
  int bsum = 0;
  if((adj[curr].size()-(int)(curr!=par))>=2){
    for(auto [to,w]:adj[curr]){
      if(to==par)continue;
      dfs(to,curr);
      int blue = dp[to][0]+w;
      int pick = dp[to][1]+w;
      if(blue>0){
        bsum+=blue;
        pick=(dp[to][1]-dp[to][0]);
      }
      //std::cout << pick << '|';
      if(mx1==-1)mx1=pick;
      else if(pick>mx1)mx2=mx1,mx1=pick;
      else if(mx2==-1)mx2=pick;
      else if(pick>mx2)mx2=pick;
    }
    if(mx1!=-1&&mx2!=-1)
    dp[curr][1]=bsum+mx1+mx2;
    else 
    dp[curr][1]=bsum;
    if(mx1!=-1)
    dp[curr][0]=bsum+mx1;
    else
    dp[curr][0]=-INF;
  }
  if((adj[curr].size()-(int)(curr!=par))==1){
    for(auto [to,w]:adj[curr]){
      if(to==par)continue;
      dp[curr][0]=dp[to][1]+w;
      dp[curr][1]=dp[to][0]+w;
    }
  }
  if((adj[curr].size()-(int)(curr!=par))==0){
    dp[curr][0]=-INF;
    dp[curr][1]=0;
  }
  //std::cout << curr << ' ' << adj[curr].size()-(int)(curr!=par) << ' ' << mx1 << ' ' << mx2 <<   ' ' << dp[curr][0] << ' ' << dp[curr][1] << '\n';
  return 0;
}
signed main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n;
  for(int i=0;i<n-1;i++){
    int x,y,c;
    std::cin >> x >> y >> c;
    adj[x].push_back({y,c});
    adj[y].push_back({x,c});
  }
  dfs(1,1);
  std::cout << dp[1][1];
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…