fork download
copy 
  1. #include<iostream>
  2. #include<utility>
  3. #include<string>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<stack>
  7. #include<vector>
  8.  
  9. using namespace std;
  10.  
  11. template <class t1, class t2>
  12. class Graph
  13. {
  14. 	public:
  15. 	vector< pair<t1,t2> > node[200005];
  16. 	int height[200005], path_length[200005]; 
  17. 	bool visited[200005];
  18. 	stack<int> stk;
  19.  
  20. 	void init()
  21. 	{
  22. 		memset(visited,false,200005);
  23. 		while(!stk.empty())
  24. 			stk.pop();
  25. 	}
  26.  
  27. 	void add_edge(int u, int v, int w)
  28. 	{
  29. 		pair<t1,t2> p;
  30. 		p = make_pair(v,w);
  31. 		node[u].push_back(p);
  32. 	}
  33.  
  34. 	void show_graph()
  35. 	{ 
  36. 		for(int i=0;i<10;i++)
  37. 		{
  38. 			int size = node[i].size();
  39. 			cout<<i<<" -> ";
  40. 			for(int j=0;j<size;j++)
  41. 				cout<<"("<<node[i][j].first<<','<<node[i][j].second<<")"<<" -> ";
  42. 			cout<<"x\n";
  43. 		}
  44. 	}
  45.  
  46. 	long long dfs(int v)
  47. 	{
  48. 		int size;
  49.  
  50. 		size = node[v].size();
  51.  
  52. 		if(size==0)
  53. 		{
  54. 			height[v] = 1;
  55. 			path_length[v] = 1;
  56. 			return height[v];
  57. 		}
  58. 		if(size == 1)
  59. 		{
  60. 			 height[v] = 1 + dfs(node[v][1].first);
  61. 			 path_length[v] = height[v];
  62. 			 return height[v];
  63. 		}
  64.  
  65. 		int temp = 0,temp1;
  66. 		height[v] = -1;
  67. 		int max1=1,max2=1;
  68.  
  69. 		for(int j=0;j<size;j++)
  70. 		{	
  71. 			if(!visited[node[v][j].first])
  72. 			{	
  73. 				visited[node[v][j].first] = true;
  74. 				temp = dfs(node[v][j].first);
  75. 				if(height[v]<temp)
  76. 					height[v] = temp;
  77. 				if(max1<temp)
  78. 				{
  79. 					temp1 = max1;
  80. 					max1 = temp;
  81. 					max2 = temp1;
  82. 				}
  83. 			}
  84. 		}
  85.  
  86. 		path_length[v] = max1 + max2 + 1;
  87.  
  88. 		return height[v];
  89. 	}	
  90. };	
  91.  
  92. int main()
  93. {
  94. 	std::ios_base::sync_with_stdio(0);
  95. 	cin.tie(0);
  96.  
  97. 	long long N,x,y,a,b;
  98.  
  99. 	cin>>N>>x>>y;
  100. 	Graph<long long,long long> G;
  101.  
  102. 	G.init();
  103.  
  104. 	for(int i=0;i<N-1;i++)
  105. 	{
  106. 		cin>>a>>b;
  107. 		G.add_edge(a,b,x);
  108. 		G.add_edge(b,a,x);
  109. 	}
  110.  
  111. 	if(x>=y)
  112. 	{
  113. 		bool flag = false;
  114. 		for(int i=1;i<=N;i++)
  115. 		{
  116. 			if(G.node[i].size()==(unsigned)(N-1))
  117. 			{
  118. 				flag = true;
  119. 				break;
  120. 			}
  121. 		}
  122.  
  123. 		if(flag)
  124. 			cout<<(N-2)*y+x<<'\n';
  125. 		else
  126. 			cout<<(N-1)*y<<'\n';
  127. 	}
  128. 	else
  129. 	{	
  130. 		G.dfs(1);
  131.  
  132. 		long long ans = -1;
  133.  
  134. 		for(int i=1;i<=N;i++)
  135. 		{
  136. 			if(ans<G.path_length[i])
  137. 				ans = G.path_length[i];
  138. 		}
  139.  
  140. 		ans--;
  141.  
  142. 		cout<<ans*x + (N-1-ans)*y<<'\n';
  143. 	}
  144.  
  145. 	return 0;
  146. }
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.  
Success #stdin #stdout 0s 6852KB
comments (?)
stdin
copy 
5 2 3
1 2
1 3
3 4
5 3
stdout
copy 
9
https://ideone.com/4yL9XS
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!