fork(2) 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 = 2e5;
  9. const int K = 2e6;
  10.  
  11. int n, k, sz[N+10], mn[K+10], timer[K+10], del[N+10], cnt, res=1e18;
  12. vector<ii> adj[N+10];
  13.  
  14. void dfs(int u, int pu){
  15.     sz[u]=1;
  16.     for (ii p: adj[u]){
  17.         int v = p.fi;
  18.         if (v==pu || del[v]) continue;
  19.         dfs(v,u);
  20.         sz[u]+=sz[v];
  21.     }
  22. }
  23.  
  24. int find_centroid(int u,int pu, int szroot){
  25.     for (ii p: adj[u]){
  26.         int v = p.fi;
  27.         if (v==pu || del[v]) continue;
  28.         if (sz[v]>szroot/2) return find_centroid(v,u, szroot);
  29.     }
  30.     return u;
  31. }
  32.  
  33.  
  34. void up(int u, int pu, int w, int d){
  35.     if (w>k) return;
  36.     if (timer[w]!= cnt) mn[w] =d;
  37.     else mn[w] = min(mn[w],d);
  38.     timer[w] = cnt;
  39.  
  40.     for (ii p: adj[u]){
  41.         int v = p.fi;
  42.         int c = p.se;
  43.  
  44.         if (v==pu || del[v]) continue;
  45.         up(v,u,w+c,d+1);
  46.     }
  47. }
  48.  
  49. void calc(int u, int pu, int w, int d){
  50.     if (w>k) return;
  51.     if (timer[k-w]==cnt) res = min(res, mn[k-w]+d);
  52.  
  53.     for (ii p: adj[u]){
  54.         int v = p.fi;
  55.         int c = p.se;
  56.  
  57.         if (v==pu || del[v]) continue;
  58.         calc(v,u,w+c,d+1);
  59.     }
  60. }
  61.  
  62. void solve(int u){
  63.     dfs(u,0);
  64.     u = find_centroid(u,0,sz[u]);
  65.     del[u]=1;
  66.  
  67.     cnt++;
  68.     timer[0] = cnt;
  69.  
  70.     for (ii p: adj[u]){
  71.         int v = p.fi;
  72.         int w = p.se;
  73.  
  74.         if (del[v]) continue;
  75.         calc(v,u,w,1);
  76.         up(v,u,w,1);
  77.     }
  78.  
  79.     for (ii p: adj[u]){
  80.         int v = p.fi;
  81.         int w = p.se;
  82.  
  83.         if (del[v]) continue;
  84.         solve(v);
  85.     }
  86. }
  87. signed main(){
  88.     ios_base::sync_with_stdio(0);
  89.     cin.tie(0); cout.tie(0);
  90.  
  91.     cin>> n>>k;
  92.     for (int i=1;i<n;i++){
  93.         int u,v,w; cin>>u>>v>>w;
  94.         adj[u].push_back({v,w});
  95.         adj[v].push_back({u,w});
  96.     }
  97.  
  98.     memset(mn,0x3f,sizeof(mn));
  99.     mn[0]=0;
  100.     solve(1);
  101.  
  102.     cout <<(res != 1e18? res:-1);
  103. }
  104.  
Success #stdin #stdout 0.01s 30244KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/yKqfeS
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!