fork download
copy 
  1. #include <iostream>
  2. #include<list>
  3. using namespace std;
  4. long long len[100001];
  5. long double ans,flag;
  6. class Graph
  7. {
  8. 	long long v;
  9. 	list<long long> *adj;
  10. 	public:
  11. 	Graph(long long v);
  12. 	void addedge(long long v,long long w);
  13. 	void BFS(long long s);
  14. };
  15.  
  16. Graph::Graph(long long v)
  17. {
  18. 	this->v=v;
  19. 	adj=new list<long long>[v];
  20. }
  21.  
  22. void Graph::addedge(long long v,long long w)
  23. {
  24. 	adj[v].push_back(w);
  25. 	adj[w].push_back(v);
  26. }
  27.  
  28. void Graph::BFS(long long s)
  29. {
  30. 	bool *visited=new bool[v];
  31. 	for(long long i=0;i<v;i++)
  32. 	visited[i]=false;
  33.  
  34. 	list<long long> queue;
  35.  
  36. 	visited[s]=true;
  37. 	queue.push_back(s);
  38. 	list<long long>::iterator i;
  39. 	long long count=0;
  40. 	while(!queue.empty())
  41. 	{
  42. 		s=queue.front();
  43. 		//cout<<s<<"  ";
  44. 		queue.pop_front();
  45. 		count=0;
  46. 		for(i=adj[s].begin();i!=adj[s].end();i++)
  47. 		{
  48. 			if(!visited[*i])
  49. 			{
  50. 				count++;   //COUNTING THE CHILDREN EXCEPT PARENT
  51. 				visited[*i]=true;
  52. 				len[*i]=len[s]+1;   //LENGTH OF THE CHILD = LENGTH OF PARENT + 1
  53. 				queue.push_back(*i);
  54. 			}
  55. 		}
  56. 		//cout<<s<<"  "<<count<<endl;
  57. 		if(count==0)     //NO CHILDREN CONDITION
  58. 		{ans+=len[s];flag++;} //INCRESING THE TOTAL LENGTH AND TOTAL LEAF NODES 
  59. 	}
  60. }
  61.  
  62. int main() {
  63. 	len[0]=0;
  64. 	ans=0;
  65. 	flag=0;
  66. 	long long n,i,j;
  67. 	cin>>n;
  68. 	Graph g(n);
  69. 	long long m=n-1;
  70. 	while(m--)
  71. 	{
  72. 		cin>>i>>j;
  73. 		g.addedge(i-1,j-1);
  74. 	}
  75. 	g.BFS(0);
  76. 	//for(i=0;i<n;i++)
  77. 	//cout<<len[i]<<"   ";
  78. 	//cout<<endl;
  79. 	cout<<fixed<<ans/flag;
  80. 	// your code goes here
  81. 	return 0;
  82. }
Runtime error #stdin #stdout 0s 16024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nUWXO5
language:
C++14 (gcc 8.3)
created:
6 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!