fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define el '\n'
  3. #define fi first
  4. #define sc second
  5. //#define int ll
  6. #define pii pair<int, int>
  7. #define all(v) v.begin(), v.end()
  8. using namespace std;
  9. using ll=long long;
  10. using ull=unsigned long long;
  11. using ld=long double;
  12. const int mod=1e9+7;
  13. const int N=2e5+11;
  14. const int lim=1e6+11;
  15. int n, k, sz[N], vit[N], dp[lim], mx;
  16. vector<int> ned;
  17. int ans=-1;
  18. vector<pii> adj[N];
  19. int subtree(int u, int pa)
  20. {
  21.     sz[u] = 1;
  22.     for (auto v: adj[u])
  23.     {
  24.         if (v.fi != pa && !vit[v.fi])
  25.         {
  26.             sz[u] += subtree(v.fi, u);
  27.         }
  28.     }
  29.     return sz[u];
  30. }
  31. int cen(int u, int pa, int n)
  32. {
  33.     for (auto v: adj[u])
  34.     {
  35.         if (v.fi != pa && !vit[v.fi] && sz[v.fi] > n/2)
  36.         {
  37.             return cen(v.fi, u, n);
  38.         }
  39.     }
  40.     return u;
  41. }
  42. void dfs(int u, int pa, int dis, int h, int ch)
  43. {
  44.     if(dis > k) return;
  45.     if(ch)
  46.     {
  47.         if(dp[dis]==-1) dp[dis]=h;
  48.         else dp[dis]=min(dp[dis], h);
  49.         ned.push_back(dis);
  50.     }
  51.     else
  52.     {
  53.         if(dp[k-dis]!=-1)
  54.         {
  55.             if(ans==-1) ans=dp[k-dis]+h;
  56.             else ans=min(ans, dp[k-dis]+h);
  57.         }
  58.     }
  59.     for(auto v: adj[u])
  60.     {
  61.         if(v.fi != pa && !vit[v.fi]) dfs(v.fi, u, dis+v.sc, h+1, ch);
  62.     }
  63. }
  64. void calc(int u)
  65. {
  66.     subtree(u, 0);
  67.     int c = cen(u, 0, sz[u]);
  68.     vit[c] = 1;
  69.     for(auto u: adj[c])
  70.     {
  71.         if (!vit[u.fi])
  72.         {
  73.             dfs(u.fi, c, u.sc, 1, 0);
  74.             dfs(u.fi, c, u.sc, 1, 1);
  75.         }
  76.     }
  77.     for(int x : ned) dp[x]=-1;
  78.     ned.clear();
  79.     for(auto v: adj[c])
  80.     {
  81.         if (!vit[v.fi])
  82.         {
  83.             calc(v.fi);
  84.         }
  85.     }
  86. }
  87. void sol()
  88. {
  89.     cin >> n >> k;
  90.     for(int i=1, u, v, x; i<n; i++)
  91.     {
  92.         cin >> u >> v >> x;
  93.         adj[u+1].push_back({v+1, x});
  94.         adj[v+1].push_back({u+1, x});
  95.     }
  96.     memset(dp, -1, sizeof dp);
  97.     dp[0]=0;
  98.     calc(1);
  99.     cout << ans;
  100. }
  101. signed main()
  102. {
  103. //    freopen("divisor.INP", "r", stdin);
  104. //    freopen("divisor.OUT", "w", stdout);
  105.     ios_base::sync_with_stdio(0);
  106.     cin.tie(0);
  107.     int t=1;
  108.     //cin >> t;
  109.     while(t--)
  110.     {
  111.         sol();
  112.     }
  113. }
  114.  
Success #stdin #stdout 0.01s 12140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/VOmd3A
language:
C++14 (gcc 8.3)
created:
1 year 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!