1 solutions
-
0tin.le LV 4 @ 2024-10-05 04:42:40
//████████╗██╗███╗░░██╗ ██╗░░░░░███████╗ //╚══██╔══╝██║████╗░██║ ██║░░░░░██╔════╝ //░░░██║░░░██║██╔██╗██║ ██║░░░░░█████╗░░ //░░░██║░░░██║██║╚████║ ██║░░░░░██╔══╝░░ //░░░██║░░░██║██║░╚███║ ███████╗███████╗ //░░░╚═╝░░░╚═╝╚═╝░░╚══╝ ╚══════╝╚══════╝ // __________________ // | ________________ | // || ____ || // || /\ | || // || /__\ | || // || / \ |____ || // ||________________|| // |__________________| // \###################\ // \###################\ // \ ____ \ // \_______\___\_______\ // An AC a day keeps the doctor away. #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define vt vector #define all(x) begin(x), end(x) #define allr(x) rbegin(x), rend(x) #define ub upper_bound #define lb lower_bound #define db double #define ld long db #define ll int64_t #define vll vt<ll> #define vvll vt<vll> #define pll pair<ll, ll> #define vpll vt<pll> #define vc vt<char> #define vvc vt<vc> #define vi vt<int> #define vvi vt<vi> #define vvvi vt<vvi> #define pii pair<int, int> #define vpii vt<pii> #define vs vt<string> #define vvs vt<vs> #define vb vt<bool> #define vvb vt<vb> #define vvpii vt<vpii> #define vd vt<db> #define ar(x) array<int, x> #define var(x) vt<ar(x)> #define pq priority_queue #define mset(m, v) memset(m, v, sizeof(m)) #define pb push_back #define ff first #define ss second #define sv string_view #define MP make_pair #define MT make_tuple #define rsz resize #define sum(x) accumulate(all(x), 0LL) #define srt(x) sort(all(x)) #define srtR(x) sort(allr(x)) #define srtU(x) sort(all(x)), (x).erase(unique(all(x)), (x).end()) #define SORTED(x) is_sorted(all(x)) #define rev(x) reverse(all(x)) #define gcd(a, b) __gcd(a, b) #define lcm(a, b) (a * b) / gcd(a, b) #define MAX(a) *max_element(all(a)) #define MIN(a) *min_element(all(a)) //SGT DEFINE #define lc i * 2 + 1 #define rc i * 2 + 2 #define lp lc, left, middle #define rp rc, middle + 1, right #define entireTree 0, 0, n - 1 #define midPoint left + (right - left) / 2 #define pushDown push(i, left, right) #define iterator int i, int left, int right #define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) struct custom { static const uint64_t C = 0x9e3779b97f4a7c15; const uint32_t RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); size_t operator()(uint64_t x) const { return __builtin_bswap64((x ^ RANDOM) * C); } size_t operator()(const std::string& s) const { size_t hash = std::hash<std::string>{}(s); return hash ^ RANDOM; } }; template <class K, class V> using umap = std::unordered_map<K, V, custom>; template <class K> using uset = std::unordered_set<K, custom>; template<typename T1, typename T2> std::ostream& operator<<(std::ostream& o, const std::pair<T1, T2>& p) { return o << "{" << p.ff << " , " << p.ss << "}"; } auto operator<<(auto &o, const auto &x) -> decltype(end(x), o) { o << "{"; int i = 0; for (const auto &e : x) { if (i++) o << " , "; o << e; } return o << "}"; } template <typename T1, typename T2> istream &operator>>(istream& in, pair<T1, T2>& input) { return in >> input.ff >> input.ss; } template <typename T> istream &operator>>(istream &in, vector<T> &v) { for (auto &el : v) in >> el; return in; } template<typename K, typename V> auto operator<<(std::ostream &o, const std::map<K, V> &m) -> std::ostream& { o << "{"; int i = 0; for (const auto &[key, value] : m) { if (i++) o << " , "; o << key << " : " << value; } return o << "}"; } template<typename T> vt<T> uniqued(vt<T> arr) { srtU(arr); return arr; } #ifdef LOCAL #define debug(x...) debug_out(#x, x) void debug_out(const char* names) { std::cerr << std::endl; } template <typename T, typename... Args> void debug_out(const char* names, T value, Args... args) { const char* comma = strchr(names, ','); std::cerr << "[" << (comma ? std::string(names, comma) : names) << " = " << value << "]"; if (sizeof...(args)) { std::cerr << ", "; debug_out(comma + 1, args...); } else { std::cerr << std::endl; } } #define startClock clock_t tStart = clock(); #define endClock std::cout << std::fixed << std::setprecision(10) << "\nTime Taken: " << (double)(clock() - tStart) / CLOCKS_PER_SEC << " seconds" << std::endl; #else #define debug(...) #define startClock #define endClock #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define eps 1e-9 #define M_PI 3.14159265358979323846 const static ll INF = 1LL << 60; const static int inf = 1e9 + 33; const static int MK = 20; const static int MX = 2e6 + 5; const static int MOD = 1e9 + 7; int pct(int x) { return __builtin_popcountll(x); } const vvi dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}}; // UP, DOWN, LEFT, RIGHT int modExpo(ll base, ll exp, ll mod) { ll res = 1; base %= mod; while(exp) { if(exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp >>= 1; } return res; } void solve() { int n; cin >> n; vvi graph(n + 1); for(int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; graph[a].pb(b); graph[b].pb(a); } vt<set<pii>> arr(n + 1); auto dfs = [&](auto& dfs, int node = 1, int par = -1) -> int { auto& curr = arr[node]; int s = 0; for(auto& nei : graph[node]) { if(nei == par) continue; int x = dfs(dfs, nei, node); curr.insert(MP(x, nei)); if(curr.size() > 2) curr.erase(*curr.begin()); s = max(s, x); } return s + 1; }; dfs(dfs); int minTime = inf, targetNode = 1; auto dfs2 = [&](auto& dfs2, int node = 1, int par = -1) -> void { auto& curr = arr[node]; while(curr.size() > 2) curr.erase(*curr.begin()); auto i = prev(curr.end()); if(i->ff < minTime || (i->ff == minTime && node > targetNode)) { minTime = i->ff; targetNode = node; } for(auto& nei : graph[node]) { if(nei == par) continue; if(!curr.empty()) { auto it = prev(curr.end()); if(it->ss == nei) { if(curr.size() > 1) { it--; arr[nei].insert(MP(it->ff + 1, node)); } else { arr[nei].insert(MP(1, node)); } } else { arr[nei].insert(MP(it->ff + 1, node)); } } dfs2(dfs2, nei, node); } }; dfs2(dfs2); if(minTime == inf) minTime = 0; cout << minTime << ' ' << targetNode << '\n'; } signed main() { IOS; startClock //generatePrime(); int t = 1; //cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; solve(); } //endClock return 0; } //███████████████████████████████████████████████████████████████████████████████████████████████████████ //█░░░░░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░███░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░░░█ //█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░░░░░░░██░░▄▀░░█░░▄▀▄▀▄▀▄▀░░░░█░░▄▀▄▀▄▀░░█░░▄▀░░░░░░░░░░██░░▄▀░░█░░▄▀▄▀▄▀▄▀▄▀░░█ //█░░▄▀░░░░░░░░░░█░░▄▀▄▀▄▀▄▀▄▀░░██░░▄▀░░█░░▄▀░░░░▄▀▄▀░░█░░░░▄▀░░░░█░░▄▀▄▀▄▀▄▀▄▀░░██░░▄▀░░█░░▄▀░░░░░░░░░░█ //█░░▄▀░░█████████░░▄▀░░░░░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░░░░░▄▀░░██░░▄▀░░█░░▄▀░░█████████ //█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░█████████ //█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░░░░░█ //█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░█ //█░░▄▀░░█████████░░▄▀░░██░░▄▀░░░░░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░░░░░▄▀░░█░░▄▀░░██░░▄▀░░█ //█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░▄▀▄▀░░█░░░░▄▀░░░░█░░▄▀░░██░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░░░▄▀░░█ //█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░██░░░░░░░░░░▄▀░░█░░▄▀▄▀▄▀▄▀░░░░█░░▄▀▄▀▄▀░░█░░▄▀░░██░░░░░░░░░░▄▀░░█░░▄▀▄▀▄▀▄▀▄▀░░█ //█░░░░░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░███░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░░░█ //███████████████████████████████████████████████████████████████████████████████████████████████████████
- 1
Information
- ID
- 1069
- Difficulty
- 7
- Category
- (None)
- Tags
- (None)
- # Submissions
- 86
- Accepted
- 19
- Accepted Ratio
- 22%
- Uploaded By