Advertisement
tumaryui

Untitled

Sep 12th, 2020
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.14 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. pii 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.first = v;
  39. del.second = pr;
  40. }
  41. }
  42.  
  43. int centroid(int v, int n, int pr = -1) {
  44. for(auto it: gr[v]) {
  45. if(it == pr) continue;
  46.  
  47. if(sz[it] > n / 2) {
  48. return centroid(it, n, v);
  49. }
  50. }
  51. for(auto it: gr[v]) {
  52. if(it != pr) {
  53. bool fine = (n - sz[it] <= n / 2);
  54. for(auto i: gr[it]) {
  55. if(i != v) {
  56. fine &= (sz[i] <= n / 2);
  57. }
  58. }
  59. if(fine) {
  60. scen = it;
  61. one = 0;
  62. }
  63. }
  64. }
  65. return v;
  66. }
  67.  
  68. void getsc(int v, int pr) {
  69. for(auto it: gr[v]) {
  70. if(it != pr) {
  71. getsc(it, v);
  72. }
  73. }
  74. if(gr[v].size() == 1) {
  75. add.sc = v;
  76. add.fr = pr;
  77. }
  78. }
  79.  
  80. void solve() {
  81. //soln
  82. int n;
  83. cin >> n;
  84. gr = vector<vector<int>> (n + 1, vector<int> ());
  85. one = 1;
  86. for(int i = 1; i <= n; i++) {
  87. sz[i] = 0;
  88. }
  89. for(int i = 1; i < n; i++) {
  90. int l, r;
  91. cin >> l >> r;
  92. gr[l].pb(r);
  93. gr[r].pb(l);
  94. }
  95.  
  96. calc(1);
  97. int cen = centroid(1, n);
  98. if(one) {
  99. yes;
  100. cout << del.fr << " " << del.sc << endl;
  101. cout << del.fr << " " << del.sc << endl;
  102. } else {
  103. getsc(scen, cen);
  104. cout << del.fr << " " << del.sc << endl;
  105. cout << add.fr << " " << add.sc << endl;
  106. }
  107. }
  108.  
  109. main() {
  110. bst;
  111. int t = 1;
  112. cin >> t;
  113. while(t--) {
  114. solve();
  115. }
  116. }
  117.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement