fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sd(mark) scanf("%d",&mark)
  5. #define ss(mark) scanf("%s",&mark)
  6. #define sl(mark) scanf("%lld",&mark)
  7. #define debug(mark) printf("check%d\n",mark)
  8. #define clr(mark) memset(mark,0,sizeof(mark))
  9. #define F first
  10. #define S second
  11. #define MP make_pair
  12. #define PB push_back
  13. #define ll long long
  14. #define INF 100000
  15. int dp1[50010][20][30],dp2[50010][20][30];
  16. int a[50010];
  17. vector<int> v[50010];
  18. int sz[50010];
  19. int ans=1,k;
  20. void go(int cur,int par)
  21. {
  22. 	int i,j,l;
  23. 	for(i=0;i<sz[cur];++i)
  24. 		if(v[cur][i]!=par)
  25. 			go(v[cur][i],cur);
  26. 	for(i=0;i<=10;++i)
  27. 		for(j=0;j<=20;++j)
  28. 			dp1[cur][i][j]=dp2[cur][i][j]=-INF;
  29.  
  30. 	for(i=0;i<k;++i)
  31. 	{
  32. 		for(j=0;j<=20;++j)
  33. 		{
  34. 			if(i==k-1&&j>a[cur])
  35. 				continue;
  36. 			int i2=k-2-i,j2=j;
  37. 			if(i==k-1)
  38. 			{
  39. 				i2=k-1;j2=a[cur];
  40. 			}
  41. 			int maxx1=-INF,maxx2=-INF;
  42. 			for(l=0;l<sz[cur];++l)
  43. 			{
  44. 				if(v[cur][l]==par)	continue;
  45. 				if(dp2[v[cur][l]][i2][j2]>maxx1)
  46. 				{
  47. 					maxx2=maxx1;
  48. 					maxx1=dp2[v[cur][l]][i2][j2];
  49. 				}
  50. 				else if(dp2[v[cur][l]][i2][j2]>maxx2)
  51. 					maxx2=dp2[v[cur][l]][i2][j2];
  52. 			}
  53. 			for(l=0;l<sz[cur];++l)
  54. 			{
  55. 				if(v[cur][l]==par)
  56. 					continue;
  57. 				if(dp2[v[cur][l]][i2][j2]!=maxx1)
  58. 					ans=max(ans,dp1[v[cur][l]][i][j]+maxx1+1);
  59. 				else
  60. 					ans=max(ans,dp1[v[cur][l]][i][j]+maxx2+1);	
  61. 			}
  62. 		}
  63. 	}
  64. 	dp1[cur][0][a[cur]]=1;
  65. 	for(j=0;j<=a[cur];++j)
  66. 		for(l=0;l<sz[cur];++l)
  67. 			if(v[cur][l]!=par)
  68. 				dp1[cur][0][a[cur]]=max(dp1[cur][0][a[cur]],1+dp1[v[cur][l]][k-1][j]);
  69. 	for(i=1;i<k;++i)
  70. 		for(j=0;j<=20;++j)
  71. 			for(l=0;l<sz[cur];++l)
  72. 				if(v[cur][l]!=par)
  73. 					dp1[cur][i][j]=max(dp1[cur][i][j],1+dp1[v[cur][l]][i-1][j]);
  74.  
  75. 	dp2[cur][0][a[cur]]=1;
  76. 	for(i=1;i<k;++i)
  77. 		dp2[cur][i][20]=1;
  78. 	for(j=a[cur];j<=20;++j)
  79. 		for(l=0;l<sz[cur];++l)
  80. 			if(v[cur][l]!=par)
  81. 				dp2[cur][0][a[cur]]=max(dp2[cur][0][a[cur]],1+dp2[v[cur][l]][k-1][j]);
  82. 	for(i=1;i<k;++i)
  83. 		for(j=0;j<=20;++j)
  84. 			for(l=0;l<sz[cur];++l)
  85. 				if(v[cur][l]!=par)
  86. 					dp2[cur][i][j]=max(dp2[cur][i][j],1+dp2[v[cur][l]][i-1][j]);
  87. 	for(i=0;i<k;++i)
  88. 		for(j=19;j>=0;--j)
  89. 			dp2[cur][i][j]=max(dp2[cur][i][j],dp2[cur][i][j+1]);
  90. 	for(i=0;i<k;++i)
  91. 		for(j=0;j<=20;++j)
  92. 			ans=max(ans,max(dp1[cur][i][j],dp2[cur][0][j]));
  93.  
  94.  
  95. }
  96. int main()
  97. {
  98. 	//freopen("in3.txt","r",stdin);
  99. 	//freopen("out3.txt","w",stdout);
  100. 	clock_t start = clock();
  101. 	int n,i,x,y;
  102. 	sd(n);sd(k);
  103. 	for(i=1;i<=n;++i)
  104. 		sd(a[i]);
  105. 	for(i=0;i<n-1;++i)
  106. 	{
  107. 		sd(x);sd(y);
  108. 		v[x].PB(y);
  109. 		v[y].PB(x);
  110. 	}
  111. 	for(i=1;i<=n;++i)
  112. 		sz[i]=v[i].size();
  113. 	go(1,0);
  114. 	printf("%d\n",ans);
  115. 	//cerr<<ans<<'\n';
  116.  
  117. 	clock_t end = clock();
  118. 	//cerr <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
  119. }
Time limit exceeded #stdin #stdout 5s 238080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3LixNa
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!