fork download
copy 
  1. //============================================================================
  2. // Name        : Brahmi Zied
  3. // Author      : brahZied
  4. // Version     : 2022
  5. // Description : Road to specialist
  6. //============================================================================
  7. /*
  8.     STAY ORGANIZED
  9.     CHANGE YOUR APPROACH
  10.     BE CONFIDENT
  11. */
  12. // when you train write the algos from 0
  13. //Think different approaches (trace TestCase,think with symbols,think with PICS,numberTheory,bs,dp,greedy,graphs,shortest paths,mst,dsu,LCA(binary lifting?))
  14. //Stay Calm
  15. // IN TRAINING DO NOT SEE WRONG TEST CASES AFTER SUBMITTING!
  16. //Look for special cases
  17. //Beware of overflow and array bounds
  18. //Think the problem backwards
  19. #include <bits/stdc++.h>
  20. using namespace std;
  21. #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  22. #define sim template < class c
  23. #define ris return * this
  24. #define dor > debug & operator <<
  25. #define eni(x) sim > typename \
  26.   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
  27. sim > struct rge { c b, e; };
  28. sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
  29. sim > auto dud(c* x) -> decltype(cerr << *x, 0);
  30. sim > char dud(...);
  31. struct debug {
  32. #ifdef LOCAL
  33. ~debug() { cerr << endl; }
  34. eni(!=) cerr << boolalpha << i; ris; }
  35. eni(==) ris << range(begin(i), end(i)); }
  36. sim, class b dor(pair < b, c > d) {
  37.   ris << "(" << d.first << ", " << d.second << ")";
  38. }
  39. sim dor(rge<c> d) {
  40.   *this << "[";
  41.   for (auto it = d.b; it != d.e; ++it)
  42.     *this << ", " + 2 * (it == d.b) << *it;
  43.   ris << "]";
  44. }
  45. #else
  46. sim dor(const c&) { ris; }
  47. #endif
  48. };
  49. #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  50.  
  51. typedef long long ll;
  52. typedef long double ld;
  53. ll n,m,k,g,a,b,d,c;
  54. const ll prime=1e9+7;
  55. const int nax=2e5+5;
  56. vector<int> adj[nax];
  57. int nodeFurthest=-1;
  58. int furthest=-1;
  59. void dfs(int node,int parent,int level){
  60.  
  61. 	if(level>=furthest){
  62. 		nodeFurthest=node;
  63. 		furthest=level;
  64. 	}
  65.  
  66. 	for(int i=0;i<(int)adj[node].size();i++){
  67. 		if(adj[node][i]!=parent){
  68. 			dfs(adj[node][i],node,level+1);
  69. 		}
  70. 	}
  71. }
  72. void dfs1(int node,int parent){
  73. 	cout << node+1 << " ";
  74.  
  75. 	for(int i=0;i<(int)adj[node].size();i++){
  76. 		if(adj[node][i]!=parent){
  77. 			dfs1(adj[node][i],node);
  78. 		}
  79. 	}
  80.  
  81. }
  82. void solve(){
  83. 	cin >> n ;
  84. 	int from,to;
  85. 	for(int i=0;i<n-1;i++){
  86. 		cin >> from >> to;
  87. 		from--;
  88. 		to--;
  89. 		adj[from].push_back(to);
  90. 		adj[to].push_back(from);
  91. 	}
  92.  
  93. 	dfs(from,-1,0);
  94.  
  95. 	dfs(nodeFurthest,-1,0);
  96. 	if(furthest<=3){
  97. 		cout << "NO"<<"\n";
  98. 		return;
  99. 	}
  100. 	int curr ,next;
  101. 	for(int i=0;i<n;i++){
  102. 		if((int)adj[i].size()<=1) continue;
  103. 		for(int j=0;j<(int)adj[i].size();j++){
  104. 			if(adj[adj[i][j]].size()>=2){
  105. 				next=adj[i][j];
  106. 				curr=i;
  107. 				break;
  108. 			}
  109. 		}
  110. 	}
  111. 	debug() << imie(curr) << imie(next);
  112. 	cout <<"YES"<<"\n";
  113. 	dfs1(curr,next);
  114. 	dfs1(next,curr);
  115. 	cout <<"\n";
  116. }
  117.  
  118. int main() {
  119. 	fastInp;
  120. 	//freopen("mootube.in","r",stdin);
  121. 	//freopen("t.out","w",stdout);
  122. 	int tc=1;
  123. 	//cout << res[9] << "\n";
  124. 	//reverse(res.begin(),res.end());
  125.  
  126. 	//cin >> tc;
  127. 	//cout << setprecision(10)<<fixed;
  128. 	//int i=1;
  129. 	//tempTC=tc;
  130. 	while(tc--){
  131. 		//cout <<"HELLO"<<endl;
  132. 		//cout << "Case #"<<i<<": " ;
  133. 		//cout << setprecision(10) << "\n";
  134. 		solve();
  135. 		//i++;
  136. 	}
  137. 	/*Slong long number;
  138. 	while(cin >> number){
  139. 		if(number==0) break;
  140. 		long long i=(long long)sqrt(number);
  141. 		if(i*i==number){
  142. 			cout <<"yes"<<"\n";
  143. 		}else{
  144. 			cout <<"no"<<"\n";
  145. 		}
  146.  
  147. 	}*/
  148.  
  149. 	/*while(true){
  150. 		cin >> n >> m >>coin;
  151.  
  152. 		if(n==0 && m==0&&coin==0){
  153. 			break;
  154. 		}
  155. 		solveUVA();
  156. 	}
  157. 	*/
  158. 	return 0;
  159. }
  160.  
Success #stdin #stdout 0.01s 8248KB
comments (?)
stdin
copy 
6
1 2
6 5
5 2
3 4
4 2
stdout
copy 
YES
5 6 2 1 4 3
https://ideone.com/0LtE25
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!