fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define db long double
  10. #define onBit(mask , i) (mask | (1 << i))
  11. #define offBit(mask , i) (mask & (~(1 << i)))
  12.  
  13. const int INF = 1e7;
  14. const int N = 2e5 + 7;
  15. int n , k , cnt = 0;
  16. long long l;
  17. int h[N] , up[21][N] , st[N] , en[N] , BIT[N];
  18. long long sum[21][N];
  19. vector<int> a[N];
  20.  
  21. void inp(){
  22. 	cin >> n >> l;
  23. 	h[1] = 1;
  24. 	for (int i = 2 ; i <= n ; ++i){
  25. 		int u;
  26. 		long long w;
  27. 		cin >> u >> w;
  28. 		h[i] = h[u] + 1;
  29. 		up[0][i] = u;
  30. 		sum[0][i] = w;
  31. 		a[i].push_back(u);
  32. 		a[u].push_back(i);
  33. 	}
  34. 	for (int j = 1 ; j <= 18 ; ++j){
  35. 		for (int i = 1 ; i <= n ; ++i){
  36. 			up[j][i] = up[j - 1][up[j - 1][i]];
  37. 			sum[j][i] = sum[j - 1][i] + sum[j - 1][up[j - 1][i]];
  38. 		}
  39. 	}
  40. }
  41.  
  42. void dfs(int u , int p){
  43. 	st[u] = ++cnt;
  44. 	for (int v : a[u]) if (v != p)
  45. 		dfs(v , u);
  46. 	en[u] = cnt;
  47. }
  48.  
  49. int far(int u){
  50. 	long long res = 0;
  51. 	for (int i = 18 ; i >= 0 ; --i){
  52. 		if (!h[up[i][u]]) continue;
  53. 		if (res + sum[i][u] > l) continue;
  54. 		res += sum[i][u];
  55. 		u = up[i][u];
  56. 	}
  57. 	return u;
  58. }
  59.  
  60. void update(int x , int val){
  61. 	if (x == 0) return;
  62. 	while (x <= n){
  63. 		BIT[x] += val;
  64. 		x += x & -x;
  65. 	}
  66. }
  67.  
  68. int get(int x){
  69. 	int res = 0;
  70. 	while (x > 0){
  71. 		res += BIT[x];
  72. 		x -= x & -x;
  73. 	}
  74. 	return res;
  75. }
  76.  
  77. void solve(){
  78. 	dfs(1 , 0);
  79. 	for (int i = 1 ; i <= n ; ++i){
  80. 		int p = far(i);
  81. 		update(st[i] , 1);
  82. 		update(st[up[0][p]] , -1);
  83. 	}
  84. 	for (int i = 1 ; i <= n ; ++i){
  85. 		cout << get(en[i]) - get(st[i] - 1) << '\n';
  86. 	}
  87. }
  88.  
  89. int main(){
  90. // 	freopen("xhmax.inp" , "r" , stdin);
  91. // 	freopen("xhmax.out" , "w" , stdout);
  92.     faster;
  93.    	inp();
  94.  	solve();
  95.     return 0;
  96. }
  97. // cnlk
Success #stdin #stdout 0.01s 15340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XWGl0H
language:
C++14 (gcc 8.3)
created:
8 hours 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!