제출 #1365044

#제출 시각아이디문제언어결과실행 시간메모리
1365044jumpBeads and wires (APIO14_beads)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
#define int long long
const int INF = 1e18;
int n;
std::vector<std::pair<int,int>> adj[205000];
int dp[205000][2];
int dfs(int curr,int par){
  std::vector<int> pk;
  int mx1=-INF,mx2=-INF;
  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 red = dp[to][1];
      int pick;
      if(red>=blue){
        pick=w;
        bsum+=red;
      }
      else{
        bsum+=blue;
        pick=(red-blue+w);
      }
      pk.push_back(pick);
      //std::cout << pick << '|';
      if(mx1==-INF)mx1=pick;
      else if(pick>mx1)mx2=mx1,mx1=pick;
      else if(mx2==-INF)mx2=pick;
      else if(pick>mx2)mx2=pick;
    }
    std::sort(pk.begin(),pk.end());
    dp[curr][1]=std::max(bsum,bsum+pk.back()+pk[pk.size()-2]);
    dp[curr][0]=bsum+pk.back();
    //dp[curr][1]=std::max(bsum,bsum+mx1+mx2);
    //dp[curr][0]=bsum+mx1;
  }
  if((adj[curr].size()-(int)(curr!=par))==1){
    for(auto [to,w]:adj[curr]){
      if(to==par)continue;
      dfs(to,curr);
      dp[curr][0]=dp[to][1]+w;
      dp[curr][1]=std::max((int)0,std::max(dp[to][1],dp[to][0]+w));
    }
  }
  if((adj[curr].size()-(int)(curr!=par))==0){
    dp[curr][0]=-INF;
    dp[curr][1]=0;
  }
  //std::cout << curr << ' ' << dp[curr][0] << ' ' << dp[curr][1] << '|';
  //for(auto p:pk)std::cout << p << ' ';
  //std::cout << '\n';
  //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];
}
/*
11
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
*/
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…