?
# | 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 |
#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;}
?
?
?
?