Advertisement
tumaryui

Untitled

Sep 12th, 2020
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.08 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. #define int long long
  8. #define pb push_back
  9. #define all(s) s.begin(),s.end()
  10. #define rall(s) s.rbegin(),s.rend()
  11. #define pii pair<int,int>
  12. #define fr first
  13. #define sc second
  14. #define bst ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  15. #define endl "\n"
  16. #define no cout << "NO" << endl;
  17. #define yes cout << "YES" << endl;
  18. typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
  19.  
  20. const int N = 5e5 + 10, mod = 1e9 + 7, inf = 1e18 + 7, logn = 23;
  21. const double pi = acos(-1);
  22.  
  23. vector<vector<int>> gr;
  24. int sz[N];
  25. bool one = 1;
  26. int scen;
  27. int del, add;
  28.  
  29. void calc(int v, int pr = -1) {
  30. sz[v] = 1;
  31. for(auto it: gr[v]) {
  32. if(it != pr) {
  33. calc(it, v);
  34. sz[v] += sz[it];
  35. }
  36. }
  37. if(gr[v].size() == 1 && pr != -1) {
  38. del = v;
  39. }
  40. }
  41.  
  42. int centroid(int v, int n, int pr = -1) {
  43. for(auto it: gr[v]) {
  44. if(it == pr) continue;
  45.  
  46. if(sz[it] > n / 2) {
  47. return centroid(it, n, v);
  48. }
  49. }
  50. for(auto it: gr[v]) {
  51. if(it != pr) {
  52. bool fine = (n - sz[it] <= n / 2);
  53. for(auto i: gr[it]) {
  54. if(i != v) {
  55. fine &= (sz[i] <= n / 2);
  56. }
  57. }
  58. if(fine) {
  59. scen = it;
  60. one = 0;
  61. }
  62. }
  63. }
  64. return v;
  65. }
  66.  
  67. void getsc(int v, int pr) {
  68. for(auto it: gr[v]) {
  69. if(it != pr) {
  70. getsc(it, v);
  71. }
  72. }
  73. if(gr[v].size() == 1) {
  74. add = v;
  75. }
  76. }
  77.  
  78. void solve() {
  79. //soln
  80. int n;
  81. cin >> n;
  82. gr = vector<vector<int>> (n + 1, vector<int> ());
  83. one = 1;
  84. for(int i = 1; i <= n; i++) {
  85. sz[i] = 0;
  86. }
  87. for(int i = 1; i < n; i++) {
  88. int l, r;
  89. cin >> l >> r;
  90. gr[l].pb(r);
  91. gr[r].pb(l);
  92. }
  93.  
  94. calc(1);
  95. int cen = centroid(1, n);
  96. if(one) {
  97. cout << del << " " << gr[del][0] << endl;
  98. cout << del << " " << gr[del][0] << endl;
  99. } else {
  100. getsc(scen, cen);
  101. cout << del << " " << gr[del][0] << endl;
  102. cout << add << " " << del << endl;
  103. }
  104. }
  105.  
  106. main() {
  107. bst;
  108. int t = 1;
  109. cin >> t;
  110. while(t--) {
  111. solve();
  112. }
  113. }
  114.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement