fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define endl '\n'
  4. #define se second
  5. #define int long long
  6. #define getName(x) #x
  7. #define vi std::vector<int>
  8. #define isz(v) (int) v.size()
  9. #define pii std::pair<int, int>
  10. #define all(v) v.begin(), v.end()
  11. #define loop cerr << "here" << endl;
  12. #define breakLoop if(TIME > 1) break;
  13. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  14. using namespace std;
  15. typedef long long ll;
  16. const int MAXN = 1e6 + 7;
  17.  
  18. template <typename T> void maximize(T &a, T b){if(a < b) a = b;}
  19. template <typename T> void minimize(T &a, T b){if(a > b) a = b;}
  20. int ans, n, sz[MAXN];
  21. vector<pii> a[MAXN];
  22. vi save; deque <int> dq;
  23.  
  24. void dfs(int u, int p, int costPar){
  25.     sz[u] = 1; bool cntOdd = 0;
  26.     for(auto i : a[u]){int v = i.fi; if(v == p)continue; dfs(v, u, i.se); sz[u] += sz[v]; if(sz[v]&1) cntOdd = 1;}
  27.     if((sz[u]&1) and cntOdd and sz[u] > 1){
  28.         save.clear(), dq.clear();
  29.         for(auto i : a[u]) if((sz[i.fi]&1) and i.fi != p) save.push_back(i.se); sort(all(save));
  30.         for(auto i : save) dq.push_back(i);
  31.         while(isz(dq)){
  32.             maximize(ans, dq.back() + dq.front());
  33.             dq.pop_back(), dq.pop_front();
  34.         }
  35.     }
  36.     else if(sz[u] % 2 == 0){
  37.         save.clear(), dq.clear(); save.push_back(costPar);
  38.         for(auto i : a[u]) if((sz[i.fi]&1) and i.fi != p) save.push_back(i.se); sort(all(save));
  39.         for(auto i : save) dq.push_back(i);
  40.         while(isz(dq)){
  41.             maximize(ans, dq.back() + dq.front());
  42.             dq.pop_back(), dq.pop_front();
  43.         }
  44.     }
  45. }
  46.  
  47. signed main(){
  48.     ios::sync_with_stdio(false);
  49.     cin.tie(nullptr);
  50.     #define task "t"
  51.     if (fopen(task".inp", "r")){
  52.         freopen(task".inp", "r", stdin);
  53.         freopen(task".out", "w", stdout);
  54.     }
  55.  
  56.     cin >> n;
  57.     for(int i = 1; i <= n - 1; i++){
  58.         int x, y, w;
  59.         cin >> x >> y >> w;
  60.         a[x].push_back({y, w});
  61.         a[y].push_back({x, w});
  62.     }
  63.     for(int i = 1; i <= n; i++) sort(all(a[i]), [&] (pii x, pii y){return x.se < y.se;});
  64.     dfs(1, -1, 0);
  65.     cout << ans;
  66.  
  67.     cerr << endl << "-------Time elapsed-------" << endl;
  68.     cerr << "          " << TIME << " s" << endl;
  69.     cerr << "--------------------------" << endl;
  70.  
  71. }
  72.  
Success #stdin #stdout #stderr 0.01s 29216KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
-------Time elapsed-------
          0.008195 s
--------------------------
https://ideone.com/CJKwgq
language:
C++14 (gcc 8.3)
created:
11 hours 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!