fork download
copy 
  1. // @adi28galaxyak
  2. // Content:
  3.  
  4. #include "bits/stdc++.h"
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef vector<int> vi;
  9. typedef vector< vi > vii;
  10. typedef pair<int, int> pii;
  11. #define FF first
  12. #define SS second
  13. #define pb(v) push_back(v)
  14. #define mp(x,y) make_pair(x, y)
  15.  
  16. #define s(n) scanf("%d",&n)
  17. #define rep(i,start,end) for(int i = start;i<end;i++)
  18.  
  19. const int MAX = 1e5;
  20. vi tree[MAX+5];
  21. vector< stack<int> > rtree(MAX+5);
  22. set<int> ans;
  23. int mh;
  24.  
  25. void ldfs(int id, int ht, int p = -1){
  26.     if(ht>mh) {
  27.         ans.insert(id);
  28.         mh = ht;
  29.     }
  30.     for(auto it: tree[id]){
  31.         if(it!=p){
  32.             ldfs(it, ht+1, id);
  33.         }
  34.     }
  35. }
  36.  
  37. void rdfs(int id, int ht, int p=-1){
  38.     if(ht>mh) {
  39.         ans.insert(id);
  40.         mh = ht;
  41.     }
  42.     while(!rtree[id].empty()){
  43.         int x = rtree[id].top();
  44.         rtree[id].pop();
  45.         if(x!=p){
  46.             rdfs(x, ht+1, id);
  47.         }
  48.     }
  49. }
  50.  
  51. int main(){
  52. 	if(false) {
  53. 		freopen("input06.txt","r",stdin);
  54. 		freopen("output06.txt","w",stdout);
  55. 	}
  56.  
  57. 	int tt;
  58. 	s(tt);
  59. 	while(tt--){
  60. 	    int n, x, y;
  61. 	    cin>>n;
  62. 	    ans.clear();
  63. 	    rep(i,1,n+5) {
  64. 	        tree[i].clear();
  65. 	        while(!rtree[i].empty()) rtree[i].pop();
  66.         }
  67.  
  68. 	    rep(i,0,n-1){
  69. 	        cin>>x>>y;
  70. 	        tree[x].pb(y);
  71. 	        tree[y].pb(x);
  72. 	        rtree[x].push(y);
  73. 	        rtree[y].push(x);
  74.         }
  75.  
  76.         mh = 0;
  77.         ldfs(1,1);
  78.         mh = 0;
  79.         rdfs(1,1);
  80.  
  81.         for(auto it: ans){
  82.             cout<<it<<" ";
  83.         }
  84.         cout<<endl;
  85.     }
  86. }
  87.  
Success #stdin #stdout 0.1s 59312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 
1
https://ideone.com/jDdbUm
language:
C++14 (gcc 8.3)
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!