Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- #define int long long
- #define pb push_back
- #define all(s) s.begin(),s.end()
- #define rall(s) s.rbegin(),s.rend()
- #define pii pair<int,int>
- #define fr first
- #define sc second
- #define bst ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- #define endl "\n"
- #define no cout << "NO" << endl;
- #define yes cout << "YES" << endl;
- typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- const int N = 5e5 + 10, mod = 1e9 + 7, inf = 1e18 + 7, logn = 23;
- const double pi = acos(-1);
- vector<int> gr;
- int sz[N];
- bool one = 1;
- int scen;
- pii del, add;
- void calc(int v, int pr = -1) {
- sz[v] = 1;
- for(auto it: gr[v]) {
- if(it != pr) {
- calc(it, v);
- sz[v] += sz[it];
- }
- }
- if(gr[v].size() == 1 && pr != -1) {
- del.first = v;
- del.second = pr;
- }
- }
- int centroid(int v, int n, int pr = -1) {
- for(auto it: gr[v]) {
- if(it == pr) continue;
- if(sz[it] > n / 2) {
- return centroid(it, n, v);
- }
- }
- for(auto it: gr[v]) {
- if(it != pr) {
- bool fine = (n - sz[it] <= n / 2);
- for(auto i: gr[it]) {
- if(i != v) {
- fine &= (sz[i] <= n / 2);
- }
- }
- if(fine) {
- scen = it;
- one = 0;
- }
- }
- }
- return v;
- }
- void getsc(int v, int pr) {
- for(auto it: gr[v]) {
- if(it != pr) {
- getsc(it, v);
- }
- }
- if(gr[v].size() == 1) {
- add.sc = v;
- add.fr = pr;
- }
- }
- void solve() {
- //soln
- int n;
- cin >> n;
- gr = vector<vector<int>> (n + 1, vector<int> ());
- one = 1;
- for(int i = 1; i <= n; i++) {
- sz[i] = 0;
- }
- for(int i = 1; i < n; i++) {
- int l, r;
- cin >> l >> r;
- gr[l].pb(r);
- gr[r].pb(l);
- }
- calc(1);
- int cen = centroid(1, n);
- if(one) {
- yes;
- cout << del.fr << " " << del.sc << endl;
- cout << del.fr << " " << del.sc << endl;
- } else {
- getsc(scen, cen);
- cout << del.fr << " " << del.sc << endl;
- cout << add.fr << " " << add.sc << endl;
- }
- }
- main() {
- bst;
- int t = 1;
- cin >> t;
- while(t--) {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement