General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
193989946 Practice:
hydra_cody
1406C - 32 C++14 (GCC 6-32) Accepted 78 ms 14644 KB 2023-02-17 15:51:09 2023-02-17 15:51:09
→ Source
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define fi first
#define se second
#define set_bits __builtin_popcountll
#define precise(ans)  cout<<fixed<<setprecision(15)<<ans
#define fo(i,n) for(ll i=0;i<n;i++)
#define Fo(i,k,n) for(ll i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define sz(x) ((ll)(x).size())
#define all(x) x.begin(), x.end()
#define PI 3.1415926535897932384626
#define MOD 1000000007
#define MOD1 998244353
typedef long long ll; typedef unsigned long long ull; typedef long double lld; typedef pair<ll, ll>  pii; typedef pair<ll, ll>    pl; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<vvi>    vvvi; typedef vector<ll>  vl; typedef vector<vl>  vvl; typedef vector<pii> vpii; typedef vector<pl>  vpl; template <typename T> using prq_mx  = priority_queue<T>; template <typename T> using prq_mn = priority_queue<T, vector<T>, greater<T>>;
const double eps = 1e-9; const ll INF = (ll) 1e9; const ll inf64 = 2e18; const ll INF64 = 9e18;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _prll(x); cerr << endl;
#else
#define debug(x)
#endif
void _prll(ll t) {cerr << t;} void _print(ll t) {cerr << t;} void _prll(string t) {cerr << t;} void _prll(char t) {cerr << t;} void _prll(lld t) {cerr << t;} void _prll(double t) {cerr << t;} void _prll(ull t) {cerr << t;} template <class T, class V> void _prll(pair <T, V> p); template <class T> void _prll(vector <T> v); template <class T> void _prll(set <T> v); template <class T, class V> void _prll(map <T, V> v); template <class T> void _prll(multiset <T> v); template <class T, class V> void _prll(pair <T, V> p) {cerr << "{"; _prll(p.fi); cerr << ","; _prll(p.se); cerr << "}";} template <class T> void _prll(vector <T> v) {cerr << "[ "; for (T i : v) {_prll(i); cerr << " ";} cerr << "]";} template <class T> void _prll(set <T> v) {cerr << "[ "; for (T i : v) {_prll(i); cerr << " ";} cerr << "]";} template <class T> void _prll(multiset <T> v) {cerr << "[ "; for (T i : v) {_prll(i); cerr << " ";} cerr << "]";} template <class T, class V> void _prll(map <T, V> v) {cerr << "[ "; for (auto i : v) {_prll(i); cerr << " ";} cerr << "]";}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
vl size,par;
ll c1,c2,c3;
vvl g;
ll n;
void dfs(ll s,ll p){
  par[s]=p;
  size[s]=1;
  ll mx=0;
  for(auto y:g[s]){
    if(y==p)continue;
    dfs(y,s);
    size[s]+=size[y];
    mx=max(mx,size[y]);
  }
  mx=max(mx,n-size[s]);
  if(mx<c3){
    c3=mx;
    c1=s;
    c2=0;
  }else if(mx==c3)c2=s;
}
void dfs2(ll s,ll p,ll& x){
  // cout<<s<<" "<<p<<endl;
  if(g[s].size()==1){
    x=s;
    return;
  }
  for(auto y:g[s]){
    if(y!=p){
      // cout<<y<<" ";
      dfs2(y,s,x);
    }
  }
}

void chal(){
  cin>>n;
  g.clear();
  size.clear();
  par.clear();
  g.resize(n+1);
  size.resize(n+1);
  par.resize(n+1);
  c3=INF;c1=0;c2=0;
  fo(i,n-1){
    ll x,y;
    cin>>x>>y;
    g[x].pb(y);
    g[y].pb(x);
  }
  debug(g);
  dfs(1,0);
  debug(par);
  if(c2==0){
    cout<<1<<" "<<g[1][0]<<endl<<1<<' '<<g[1][0]<<endl;
    // cout<<endl;
    return;
  }
  // cout<<c1<<" "<<c2<<endl;
  if(par[c1]!=c2)swap(c1,c2);
  ll x=0;
  dfs2(c1,c2,x);
  cout<<x<<" "<<par[x]<<endl;
  cout<<c2<<" "<<x<<endl;
  // cout<<endl;





  

}







//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int32_t main() {ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); srand(chrono::high_resolution_clock::now().time_since_epoch().count());
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); freopen("Error.txt", "w", stderr);
#endif
  ll  t; t = 1;
  cin >> t;
  for (ll i = 1; i <= t; i++) {chal();} return 0;}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details