fork download 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef long long ll;
  7. typedef long double ld;
  8. typedef pair<int, int> pii;
  9. typedef pair<ll, ll> pll;
  10. typedef vector<int> vi;
  11. typedef vector<ll> vll;
  12. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  13. #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
  14. #define pb push_back
  15. #define ff first
  16. #define ss second
  17.  
  18. const int N = 2e5 + 1;
  19. vector<pll> graf[N], odl[N];
  20. vi zb;
  21. ll dyst[N];
  22. int podd[N], odw[N];
  23.  
  24.  
  25. struct oba{
  26.     ll v1, k1, v2, k2;
  27. };
  28.  
  29. vector<oba> pref[N], suf[N];
  30.  
  31. void poddrzewa(int v, int ojc){
  32.     podd[v] = 1;
  33.     for(pll x : graf[v]){
  34.         int u = x.ff;
  35.         if(odw[u] || u == ojc) continue;
  36.         poddrzewa(u, v);
  37.         podd[v] += podd[u];
  38.     }
  39. }
  40.  
  41. int znajdz(int v, int ojc, int r){
  42.     for(pll x : graf[v]){
  43.         int u = x.ff;
  44.         if(odw[u] || u == ojc) continue;
  45.         if(podd[u] > r / 2) return znajdz(u, v, r);
  46.     }
  47.     if(r - podd[v] <= r / 2) return v;
  48. }
  49.  
  50. void dfs_policz(int v, int ojc){
  51.     zb.pb(v);
  52.     for(pll x : graf[v]){
  53.         int u = x.ff;
  54.         if(u == ojc || odw[u]) continue;
  55.         dyst[u] = dyst[v] + x.ss;
  56.         dfs_policz(u, v);
  57.     }
  58. }
  59.  
  60. void decompose(int v){
  61.     poddrzewa(v, 0);
  62.     int c = znajdz(v, 0, podd[v]);
  63.     odw[c] = 1; dyst[c] = 0;
  64.     odl[c].pb({0, c});
  65.     for(pll x : graf[c]){
  66.         int u = x.ff; ll w = x.ss;
  67.         if(odw[u]) continue;
  68.         dyst[u] = w;
  69.         dfs_policz(u, 0);
  70.  
  71.         for(int y : zb){
  72.             odl[c].pb({dyst[y], u});
  73.         }
  74.     }
  75.  
  76.     sort(odl[c].begin(), odl[c].end());
  77.     pref[c].resize(podd[v] + 1);
  78.     suf[c].resize(podd[v] + 1);
  79.     pref[c][0] = {-1, -2, -1, -1};
  80.     for(int i = 1; i <= odl[c].size(); i++){
  81.         ll d = odl[c][i].ff, k = odl[c][i].ss;
  82.         if(k == pref[c][i - 1].k1){
  83.             pref[c][i].v2 = pref[c][i - 1].v2; pref[c][i].k2 = pref[c][i - 1].k2;
  84.         }else{
  85.             pref[c][i].v2 = pref[c][i - 1].v1; pref[c][i].k2 = pref[c][i - 1].v1;
  86.         }
  87.         pref[c][i].v1 = d; pref[c][i].k1 = k;
  88.     }
  89.  
  90.  
  91.  
  92.     for(pii x : graf[c]){
  93.         if(odw[x.ff]) continue;
  94.         decompose(x.ff);
  95.     }
  96. }
  97.  
  98.  
  99. ll mniej(ll x, int n){
  100.     ll best = -1;
  101.     for(int c = 1; c <= n; c++){
  102.         int m = odl[c].size();
  103.         int j = m;
  104.         for(int i = 1; i <= m; i++){
  105.             while(j >= 1 && odl[c][i - 1].ff + odl[c][j - 1].ff > x) j--;
  106.             if(j == 0) break;
  107.  
  108.             ll kand = odl[c][i - 1].ff, k = odl[c][i - 1].ss;
  109.             if(k == pref[c][j].k1){
  110.                 kand += pref[c][j].v2;
  111.             }else{
  112.                 kand += pref[c][j].v1;
  113.             }
  114.  
  115.             best = max(kand, best);
  116.  
  117.         }
  118.     }
  119.     return best;
  120. }
  121.  
  122. ll wiecej(ll x, int n){
  123.  
  124.  
  125. }
  126.  
  127.  
  128.  
  129. int main(){
  130.     ios_base::sync_with_stdio(0);
  131.     cin.tie(0);
  132.  
  133.     int n, q;
  134.     cin >> n >> q;
  135.  
  136.     for(int i = 1; i < n; i++){
  137.         int a, b, c; cin >> a >> b >> c;
  138.         graf[a].pb({b, c}); graf[b].pb({a, c});
  139.     }
  140.  
  141.     decompose(1);
  142.  
  143.     vector<pll> przedzialy;
  144.     ll pocz, kon;
  145.  
  146.  
  147.     while(q--){
  148.  
  149.     }
  150.  
  151.  
  152.  
  153.     return 0;
  154. }
  155.  
  156.  
Success #stdin #stdout 0.01s 25720KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/9rj4z0
language:
C++14 (gcc 8.3)
created:
3 days 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!