fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dp[100005][3]={0};
  4. vector<int>v[100005];
  5. bool vis[100005];
  6. void ins(int n)
  7. {
  8. int i;
  9. for(i=0;i<n+100;i++)
  10. vis[i]=false;
  11. }
  12. void dfs(int i)
  13. {
  14. int j;
  15. vis[i]=true;
  16. for(j=0;j<v[i].size();j++)
  17. {
  18. if(vis[v[i][j]]==false)
  19. {
  20. dfs(v[i][j]);
  21. dp[i][0]+=dp[v[i][j]][1];
  22. dp[i][1]+=min(dp[v[i][j]][1],dp[v[i][j]][0]);
  23. }
  24. }
  25. dp[i][1]++;
  26. }
  27. int main()
  28. {
  29. int n,i,x,y;
  30. cin>>n;
  31. for(i=0;i<n-1;i++)
  32. {
  33. cin>>x>>y;
  34. v[x].push_back(y);
  35. v[y].push_back(x);
  36. }
  37. ins(n);
  38. dfs(1);
  39. cout<<min(dp[1][0],dp[1][1])<<endl;
  40. return 0;
  41. }
Success #stdin #stdout 0s 5960KB
stdin
13
1 2
1 3
1 4
1 5
1 6
1 7
2 8
2 9
2 10
2 11
2 12
2 13
stdout
2