fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. #include <map>
  5. using namespace std;
  6.  
  7. long long DP[2][200005];
  8. vector<long long> adj[200005];
  9.  
  10. void DFS(long long u,long long p)
  11. {
  12. 	DP[0][u] = 0;
  13. 	DP[1][u] = LLONG_MIN;
  14.  
  15. 	for(int i=0;i<adj[u].size();i++)
  16. 	{
  17. 		long long v = adj[u][i];
  18. 		if(v == p)
  19. 		{
  20. 			continue;
  21. 		}
  22.  
  23. 		DFS(v,u);
  24.  
  25. 		DP[0][u] += max(DP[0][v],DP[1][v]);
  26. 		DP[1][u] = max(DP[1][u],min(DP[0][v]-DP[1][v],(long long)0));
  27.  
  28. 	}
  29. 	DP[1][u]+=DP[0][u];
  30. 	DP[1][u]++;
  31. }
  32.  
  33.  
  34. int main() {
  35.  
  36. 	int n;
  37. 	cin>>n;
  38.  
  39. 	for(int i=0;i<n-1;i++)
  40. 	{
  41. 		int a,b;
  42. 		cin>>a>>b;
  43.  
  44. 		adj[a-1].push_back(b-1);
  45. 		adj[b-1].push_back(a-1);
  46. 	}
  47.  
  48. 	DFS(0,-1);
  49.  
  50. 	cout<<max(DP[0][0],DP[1][0])<<endl;
  51.  
  52. 	return 0;
  53. }
Success #stdin #stdout 0.01s 9420KB
comments (?)
stdin
copy 
5
1 2
1 3
3 4
3 5
stdout
copy 
2
https://ideone.com/4MKvgd
language:
C++14 (gcc 8.3)
created:
11 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!