fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define endl "\n"
  5. #define pll pair<long long,long long>
  6. #define pii pair<int,int>
  7.  
  8. const long long MOD = 1e9+7; 
  9.  
  10. using namespace std;
  11. int n;
  12.  
  13. vector<pll> adj[200005];
  14. int deg[200005];
  15. ll dp[2][200005];// 1: 1 day, 0, sao cx dc
  16. bool ok[200005];
  17.  
  18. void dfs(ll a){
  19.     if (ok[a]) return;
  20.     ok[a]=1;
  21.     if (deg[a]==1 && a!=1){
  22.         dp[1][a]=0;
  23.         dp[0][a]=0;
  24.         return;
  25.     }
  26.     vector<pll> tmp;
  27.     for (auto x:adj[a]){
  28.         if (ok[x.first]) continue;
  29.         dfs(x.first);
  30.         dp[1][a]=max(dp[1][a],dp[1][x.first]+x.second);
  31.         tmp.push_back({dp[1][x.first]+x.second,x.second});
  32.     }
  33.     sort(tmp.begin(),tmp.end(),greater<pll>());
  34.     if (tmp.size()<=1){
  35.         dp[0][a]=dp[1][a];
  36.         return;
  37.     }
  38.     dp[0][a]=tmp[0].first+tmp[1].first;
  39. }
  40.  
  41. int main(){
  42.     ios_base::sync_with_stdio(0);
  43.     cin.tie(NULL);
  44.     cout.tie(NULL);
  45.     if(fopen("input.txt", "r")) {
  46.         freopen("input.txt","r",stdin);
  47.         freopen("output.txt","w",stdout);
  48.     }
  49.     int k;
  50.     cin>>n>>k;
  51.     ll res1=0;
  52.     for (int i=1; i<n; i++){
  53.         int a,b,c;
  54.         cin>>a>>b>>c;
  55.         adj[a].push_back({b,c});
  56.         adj[b].push_back({a,c});
  57.         deg[a]++;
  58.         deg[b]++;
  59.         res1+=c;
  60.     }
  61.     if (k>=2) {
  62.         cout<<res1<<endl;
  63.         return 0;
  64.     }
  65.     dfs(1);
  66.     res1=0;
  67.     for (int i =1; i<=n; i++){
  68.         res1=max(res1,dp[0][i]);
  69.     }
  70.     cout<<res1<<endl;
  71.     return 0;
  72. }
Success #stdin #stdout 0.01s 9708KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/030oAl
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!