fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define ll long long
  6. #define bit(n, i) ((n >> i) & 1)
  7. #define all(a) a.begin(), a.end()
  8. #define rep(i, x, n) for (int i = x; i <= n; ++i)
  9. #define red(i, x, n) for (int i = x; i >= n; --i)
  10. #define inp(a) if (fopen(a".inp", "r")) freopen(a".inp", "r", stdin), freopen(a".out", "w", stdout)
  11.  
  12. template<class A, class B> inline bool maxi(A &x, B y) {return (x < y ? x = y, 1 : 0);};
  13. template<class A, class B> inline bool mini(A &x, B y) {return (x > y ? x = y, 1 : 0);};
  14.  
  15. const int N = 1e5 + 5;
  16. const ll MOD = 1e9 + 7;
  17. const ll INF = LLONG_MAX;
  18.  
  19. // main program
  20.  
  21. struct node {int v, w;};
  22.  
  23. int n, k;
  24. vector<node> a[N];
  25.  
  26. int sz[N], process[N];
  27.  
  28. int countChild(int u, int p){
  29.     sz[u] = 1;
  30.  
  31.     for (auto [v, w]: a[u]){
  32.         if (v != p || process[v]) continue;
  33.  
  34.         sz[u] += countChild(v, u);
  35.     }
  36.  
  37.     return sz[u];
  38. }
  39.  
  40. int centroid(int u, int p, int n){
  41.     for (auto [v, w]: a[u]){
  42.         if (v == p || process[v]) continue;
  43.  
  44.         if (sz[v] > n / 2) return centroid(v, u, n);
  45.     }
  46.  
  47.     return u;
  48. }
  49.  
  50. ll ans = 0;
  51. vector<int> depth;
  52.  
  53. int get(int x){
  54.     return upper_bound(all(depth), x) - depth.begin();
  55. }
  56.  
  57. void dfs(int u, int p, int d, bool add){
  58.     if (d > k) return;
  59.  
  60.     if (add) depth.pb(d);
  61.     else ans += get(k - d);
  62.  
  63.     for (auto [v, w]: a[u]){
  64.         if (v == p || process[v]) continue;
  65.  
  66.         dfs(v, u, d + w, add);
  67.     }
  68. }
  69.  
  70. void updateANS(int u){
  71.     depth = {0};
  72.  
  73.     for (auto [v, w]: a[u]){
  74.         if (process[v]) continue;
  75.  
  76.         dfs(v, u, w, 0);
  77.         dfs(v, u, w, 1);
  78.         sort(all(depth));
  79.     }
  80. }
  81.  
  82. void decompose(int u){
  83.     int n = countChild(u, 0);
  84.     u = centroid(u, 0, n);
  85.  
  86.     updateANS(u); process[u] = 1;
  87.  
  88.     for (auto [v, w]: a[u]) if (process[v] == 0){
  89.         decompose(v);
  90.     }
  91. }
  92. signed main(){
  93.     cin.tie(0) -> sync_with_stdio(0);
  94.  
  95.     cin >>n >>k;
  96.  
  97.     rep(i, 2, n){
  98.         int u, v, w; cin >>u >>v >>w;
  99.  
  100.         a[u].pb({v, w}); a[v].pb({u, w});
  101.     }
  102.  
  103.     decompose(1);
  104.  
  105.     cout <<ans;
  106.  
  107.     return 0;
  108. }
Success #stdin #stdout 0.01s 5908KB
comments (?)
stdin
copy 
7 10
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
stdout
copy 
5
https://ideone.com/Vx3a3u
language:
C++ (gcc 8.3)
created:
10 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!