fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector < vector < pair<int,int> > > G;
  4. int n,q,dp[105][105];
  5. void dfs(int pos, int par)
  6. {
  7. 	//pos is where i am currently
  8. 	//par is my parent
  9. 	int dp_v[n+2][n+2];
  10. 	memset(dp_v, -1, sizeof dp_v); //-1 means not computed
  11.  
  12. 	//best we can do after considering 0 children and 0 edges is 0
  13. 	dp_v[0][0]=0;
  14.  
  15. 	int child_num=1;
  16. 	for (int i = 0; i < G[pos].size(); ++i)
  17. 	{
  18. 		int child=G[pos][i].first;
  19. 		int weight_of=G[pos][i].second;
  20. 		//since we added edges in both directions we
  21. 		//must ensure that we are travelling down the tree
  22. 		//and not up the tree. if child is not equal to par then
  23. 		//we are going down
  24. 		if(child != par)
  25. 		{
  26. 			//parent of child is where i am i.e. pos
  27. 			dfs(child,pos);
  28. 			//now that I have processed this child
  29. 			//i can compute dp_v(child_num,j)
  30. 			for (int j = 0; j < n; ++j)
  31. 			{
  32. 				if(dp_v[child_num-1][j] != -1)
  33. 					dp_v[child_num][j] = dp_v[child_num-1][j];
  34. 				for (int k = 0; k < j; ++k)
  35. 				{
  36. 					if(dp_v[child_num-1][j-(k+1)] != -1)
  37. 						dp_v[child_num][j]=max(dp_v[child_num][j],dp_v[child_num-1][j-(k+1)] + weight_of + dp[child][k]);
  38. 				}
  39. 			}
  40. 			//update child_num
  41. 			child_num++;
  42. 		}
  43. 	}
  44. 	for (int i = 0; i < n; ++i)
  45. 	{
  46. 		dp[pos][i]=dp_v[child_num-1][i];
  47. 	}
  48. }
  49. int main()
  50. {
  51. 	ios_base::sync_with_stdio(0);
  52. 	cin>>n>>q;
  53. 	G.resize(n+1);
  54. 	int u,v,w;
  55. 	for (int i = 0; i < n-1; ++i)
  56. 	{
  57. 		cin>>u>>v>>w;
  58. 		G[u].push_back(make_pair(v,w));
  59. 		G[v].push_back(make_pair(u,w));
  60. 	}
  61. 	//compute dp inside dfs
  62. 	dfs(1,0);
  63. 	//final answer is the best subtree rooted at 1 with q edges
  64. 	cout<<dp[1][q]<<"\n";
  65. 	return 0;
  66. }
Success #stdin #stdout 0s 3324KB
comments (?)
stdin
copy 
5 2
1 3 1
1 4 10
2 3 20
3 5 20
stdout
copy 
21
https://ideone.com/e2MEG9
language:
C++ (gcc 8.3)
created:
9 years 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!