fork(1) download
  1. #include<iostream>
  2. #include <queue>
  3. #define ll long long int
  4. using namespace std;
  5. int main(){
  6. ll n,r,c;
  7. cin>>n;
  8. ll g[n][n],visited[n],lastnode,sum=0,a,b;
  9. for(ll i=0;i<n;i++)
  10. for(ll j=0;j<n;j++)
  11. if(i==j)
  12. g[i][j]=0;
  13. else
  14. g[i][j]=-1;
  15. for(ll i=0;i<n-1;i++){
  16. cin>>a>>b;
  17. g[a-1][b-1]=1;
  18. g[b-1][a-1]=1;
  19. }
  20. for(ll i=0;i<n;i++)
  21. visited[i]=0;
  22. queue<ll> q;
  23. q.push(0);
  24. visited[0]=1;
  25. while(!q.empty()){
  26. r=q.front();
  27. q.pop();
  28. for(ll i=0;i<n;i++)
  29. if(g[r][i]==1 && !visited[i]){
  30. q.push(i);
  31. visited[i]=1;
  32. }
  33. }
  34. lastnode=r;
  35. for(ll i=0;i<n;i++)
  36. visited[i]=0;
  37. visited[r]=1;
  38. q.push(r);
  39. while(!q.empty()){
  40. lastnode=q.front();
  41. q.pop();
  42. c=0;
  43. for(ll i=0;i<n;i++)
  44. if(g[lastnode][i]==1 && !visited[i]){
  45. if(c==0){
  46. sum++;
  47. c=1;
  48. }
  49. visited[i]=1;
  50. q.push(i);
  51. }
  52. }
  53. cout<<sum;
  54. return 0;
  55. }
Success #stdin #stdout 0s 3468KB
stdin
3
1 2
2 3
stdout
2