Problem Solution

1 solutions

  • 0
    @ 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