제출 #1296652

#제출 시각아이디문제언어결과실행 시간메모리
1296652uranium235Hard route (IZhO17_road)C++17
100 / 100
674 ms199412 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <class a, class b> ostream& operator<<(ostream &l, const pair<a, b> &r) {
    l << "(" << r.first << ", " << r.second << ")";
    return l;
}

template <class t> ostream& operator<<(ostream &l, const vector<t> &r) {
    l << "{";
    for (int i = 0; i + 1 < r.size(); i++) l << r[i] << ", ";
    if (!r.empty()) l << r.back();
    l << "}";
    return l;
}

template <class t> void comb(pair<t, t> &l, const pair<t, t> &r) {
    // cout << "comb " << l.first << " " << l.second << " " << r.first << " " << r.second << endl;
    if (r.second == 0) return;
    if (l.first == r.first) l.second += r.second;
    else if (l.first < r.first) l = r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<vector<pair<int, int>>> depths(n);
    auto dfs = [&](int v, int p, auto &&self) -> pair<int, int> {
        pair<int, int> cur{0, 1};
        for (int i : adj[v]) {
            if (i != p) {
                pair<int, int> ts = self(i, v, self);
                ts.first++;
                depths[v].push_back(ts);
                comb(cur, ts);
            }
        }
        return cur;
    };
    dfs(0, -1, dfs);

    vector<pair<int, int>> pd(n, {0, 1});
    auto dfs1 = [&](int v, int p, auto &&self) -> void {
        map<int, int> freq;
        for (pair<int, int> &i : depths[v]) {
            freq[i.first] += i.second;
        }

        int ptr = 0;
        for (int i : adj[v]) {
            if (i != p) {
                pair<int, int> d = depths[v][ptr];
                int rem = (freq[d.first] -= d.second);
                if (rem == 0) freq.erase(d.first);

                pd[i] = pd[v];
                if (!freq.empty()) {
                    reverse_iterator<map<int, int>::iterator> it = freq.rbegin();
                    comb(pd[i], { it->first, it->second });
                }
                pd[i].first++;


                freq[d.first] += d.second;
                ptr++;
            }
        }

        for (int i : adj[v]) {
            if (i != p) {
                self(i, v, self);
            }
        }
    };
    dfs1(0, -1, dfs1);
    // cout << pd << endl;

    pair<ll, ll> ans{0, 1};
    for (int i = 0; i < n; i++) {
        vector<pair<int, int>> &depth = depths[i];
        if (i != 0) {
          depth.push_back(pd[i]);
        }
        sort(depth.rbegin(), depth.rend());

        // cout << "-------------" << i << " " << depths.size() << endl;
        
        if (depth.size() > 2) {
            // 0 and 1 as paths
            comb(ans, {ll(depth[0].first + depth[1].first) * depth[2].first, ll(depth[0].second * depth[1].second)});

            pair<int, int> pref = depth[1];
            for (int j = 2; j < depth.size(); j++) {
                // 0 and j as paths(padding doesn't change anything here, it's fine if depth[2].first = 0)
                comb(ans, {ll(depth[0].first + depth[2].first) * depth[1].first, ll(depth[0].second) * depth[2].second});
                
                // 0 is farthest, i < j as paths
                comb(ans, {ll(depth[j].first + pref.first) * depth[0].first, ll(pref.second) * depth[j].second });
                comb(pref, depth[j]);
            }
        }
        // cout << "-------------" << i << " " << depths << endl;

        //
    }

    cout << ans.first << " " << ans.second << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...