Advertisement
jeff69

Untitled

Jun 30th, 2016
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. int n;
  6. vector<int> adj[100007];
  7.  
  8. int coun=1;
  9. int dfs(int x,int pa)
  10. {
  11.  
  12. int ans=0;
  13. for(int i=0;i<adj[x].size();i++)
  14. {
  15. int y=adj[x][i];
  16. if(y==pa)continue;
  17. coun=1-coun;
  18. // if(coun)cout<<x<<' '<<y<<endl;
  19. ans+=dfs(y,x)+coun;
  20. coun=1-coun;
  21.  
  22. }
  23.  
  24. return ans;
  25. }
  26. int main()
  27. {
  28. cin>>n;
  29. if(n==1)
  30. {
  31. cout<<0;
  32. return 0;
  33. }
  34. for(int i=1;i<n;i++)
  35. {
  36. int x,y;
  37. cin>>x>>y;
  38. adj[x].push_back(y);
  39. adj[y].push_back(x);
  40.  
  41. }
  42. int w=0,v=1;
  43. for(int i=1;i<=n;i++)
  44. {
  45. if(adj[i].size()>w)
  46. {
  47. w=adj[i].size();
  48. v=i;
  49. }
  50. }
  51. // cout<<v<<'\n';
  52. cout<<1+dfs(v,0);
  53.  
  54.  
  55. return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement