fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <set>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <iostream>
  7. #define MAXN 200005
  8. #define fr first
  9. #define sc second
  10. #define mp make_pair
  11. using namespace std;
  12. int n,cevap[MAXN];
  13. long long k,dp[MAXN];
  14. priority_queue <long long> q[MAXN];
  15. vector <pair <int,long long> > v[MAXN];
  16. inline void fun(int x)
  17. {
  18. 	q[x].push(dp[x]);
  19. 	for(int i=0;i<(int)v[x].size();i++)
  20. 	{
  21. 		fun(v[x][i].fr);
  22. 		if(q[x].size()<q[v[x][i].fr].size()) swap(q[x],q[v[x][i].fr]);
  23. 		while(!q[v[x][i].fr].empty())
  24. 		{
  25. 			q[x].push(q[v[x][i].fr].top());
  26. 			q[v[x][i].fr].pop();
  27. 		}
  28. 	}
  29. 	while(!q[x].empty() && q[x].top()-dp[x]>k) q[x].pop();
  30. 	cevap[x]=q[x].size();
  31. }
  32. inline void dfs(int x,long long dep)
  33. {
  34. 	dp[x]=dep;
  35. 	for(int i=0;i<(int)v[x].size();i++)
  36. 		dfs(v[x][i].fr,dep+v[x][i].sc);
  37. }
  38. int main()
  39. {
  40. 	freopen("runaway.in","r",stdin);
  41. 	freopen("runaway.out","w",stdout);
  42. 	scanf("%d %lld",&n,&k);
  43. 	for(int i=1,a;i<n;i++)
  44. 	{
  45. 		long long b;
  46. 		scanf("%d %lld",&a,&b);
  47. 		v[a].push_back(mp(i+1,b));
  48. 	}
  49. 	dfs(1,0);
  50. 	fun(1);
  51. 	for(int i=1;i<=n;i++)
  52. 		printf("%d\n",cevap[i]);
  53. }
  54. /*
  55. 4 5
  56. 1 4
  57. 2 3
  58. 1 5
  59.  
  60. */
  61.  
Success #stdin #stdout 0s 11288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2bjocS
language:
C++ (gcc 8.3)
created:
9 years 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!