fork download 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define ii pair<int,int>
  4. #define fi first
  5. #define se second
  6.  
  7. using namespace std;
  8. const int N = 1e6;
  9. const int K = 1e6;
  10. const int INF = 1e9;
  11.  
  12. int n, k, sz[N+10], bigc[N+10], st[N+10], fst[N+10], en[N+10], f[N+10], h[N+10], timer, res = INF;
  13. vector<ii> adj[N+10];
  14. map<int,int> mn;
  15.  
  16. void dfs(int u, int pu){
  17.     sz[u]=1;
  18.     st[u] = ++timer;
  19.     fst[timer] = u;
  20.  
  21.     for (ii p: adj[u]){
  22.         int v = p.fi;
  23.         int w = p.se;
  24.         if (v==pu) continue;
  25.         f[v] = f[u]+w;
  26.         h[v] = h[u]+1;
  27.         if (f[v]==k) res = min(res, h[v]);
  28.         dfs(v,u);
  29.         sz[u]+=sz[v];
  30.  
  31.         if (sz[v]>sz[bigc[u]]) bigc[u]=v;
  32.     }
  33.     en[u] = timer;
  34. }
  35.  
  36. void sackadd(int u){
  37.     if (!mn[f[u]]) mn[f[u]]=INF;
  38.     mn[f[u]] = min(mn[f[u]], h[u]);
  39. }
  40.  
  41. void sacksub(int u){
  42.     mn[f[u]] = INF;
  43. }
  44.  
  45. void Sack(int u, int pu){
  46.     for (ii p: adj[u]){
  47.         int v = p.fi;
  48.         if (v==pu || v==bigc[u]) continue;
  49.         Sack(v,u);
  50.         for (int i=st[v];i<=en[v];i++) sacksub(fst[i]);
  51.     }
  52.  
  53.     if (bigc[u]) Sack(bigc[u], u);
  54.     if (mn[f[u]+k]==0) mn[f[u]+k] = INF;
  55.     res = min(res, mn[f[u]+k]-h[u]);
  56.  
  57.     sackadd(u);
  58.     for (ii p: adj[u]){
  59.         int v = p.fi;
  60.         if (v==pu || v==bigc[u]) continue;
  61.         for (int i=st[v];i<=en[v];i++){
  62.             int c = k-(f[fst[i]]-f[u])+f[u];
  63.             if (mn[c]==0) mn[c] =INF;
  64.             if (c>=0) res = min(res, mn[c]+h[fst[i]]-2*h[u]);
  65.         }
  66.         for (int i=st[v];i<=en[v];i++) sackadd(fst[i]);
  67.     }
  68. }
  69. signed main(){
  70.     ios_base::sync_with_stdio(0);
  71.     cin.tie(0); cout.tie(0);
  72.  
  73.     cin>>n>>k;
  74.     for (int i=1;i<n;i++){
  75.         int u,v,w; cin>> u>>v>>w;
  76.         u++; v++;
  77.         adj[u].push_back({v,w});
  78.         adj[v].push_back({u,w});
  79.     }
  80.  
  81.     dfs(1,0);
  82.     Sack(1,0);
  83.     cout <<(res>=2e5?-1:res);
  84. }
  85.  
Success #stdin #stdout 0.01s 35996KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/oBpkq3
language:
C++14 (gcc 8.3)
created:
129 days ago
visibility:
secret

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!