fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef vector<string> vs;
  4. typedef vector<vector<int>> vvi;
  5. typedef vector<list<int>> vli; 
  6. typedef vector<int> vi;
  7. typedef pair<int,int> pii;
  8. typedef vector<string> vs;
  9. typedef vector<bool> vb;
  10. typedef long long ll;
  11. typedef double db;
  12. typedef priority_queue<int> pq;
  13. typedef vector<vector<pii>> vvp;
  14. typedef vector<pii> vpi;
  15. #define fi first
  16. #define se second
  17. #define FOR(i,s,e,d) for(int i=s;i<e;i+=d)
  18. #define FORL(i,s,e,d) for(ll i=s;i<e;i+=d)
  19. #define RFOR(i,s,e,d) for(int i=s;i>=e;i+=d)
  20. #define RFORL(i,s,e,d) for(ll i=s;i>=e;i+=d)
  21. const int maxD=1000001;
  22. const int INF=1e9;
  23. // 양방향 graph
  24. int n;
  25. vi adj[maxD], child[maxD];
  26. int dp[maxD][2]; // 선택하느냐 안하느냐
  27. bool visit[maxD];
  28. bool dfs(int here){ // child 탐색
  29. 	visit[here]=true;
  30. 	for(int next:adj[here])
  31. 		if(!visit[next]){
  32. 			child[here].push_back(next);
  33. 			dfs(next);
  34. 		}
  35. }
  36. int solve(int here, bool bead){
  37. 	// 부모가 ad인지 아닌지에 주어질 때 here 포함 아래 서브트리 내 필요한 
  38. 	// 최소 어답터 수 구함
  39. 	// 0이면 false, 1이면 true
  40. 	int& ret=dp[here][bead];
  41. 	if(ret!=-1)
  42. 		return ret;
  43. 	// 두 가지 선택지
  44. 	// bead가 false면 무조건 pick
  45. 	int pick=1, npick=INF;
  46. 	for(int next:child[here])
  47. 		pick+=solve(next,true);
  48. 	if(bead){
  49. 		npick=0;
  50. 		for(int next:child[here])
  51. 			npick+=solve(next,false);
  52. 	}
  53. 	return ret=min(pick,npick);
  54. }
  55. int main(){
  56. 	cin.tie(NULL);
  57. 	cout.tie(NULL);
  58. 	ios_base::sync_with_stdio(false);
  59. 	cin>>n;
  60. 	FOR(i,0,n-1,1){
  61. 		int a,b;
  62. 		cin>>a>>b;
  63. 		// 양방향
  64. 		adj[a].push_back(b);
  65. 		adj[b].push_back(a);
  66. 	}
  67. 	int test[5];
  68. 	FOR(i,0,5,1)
  69. 		cout<<"test : "<<test[i]<<'\n';
  70. 	dfs(1); // 1에서 시작하는 dfs
  71. 	memset(dp,-1,sizeof(dp)); // byte 크기로 채움
  72. 	cout<<solve(1,true)<<'\n';
  73. 	return 0;
  74. }
Success #stdin #stdout 0.01s 70912KB
comments (?)
stdin
copy 
8
1 2
1 3
1 4
2 5
2 6
4 7
4 8
stdout
copy 
test : 8
test : 0
test : 2
test : 0
test : -1239843448
3
https://ideone.com/Sa7Wla
language:
C++14 (gcc 8.3)
created:
4 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!