Submission #1296649

#TimeUsernameProblemLanguageResultExecution timeMemory
1296649uranium235Hard route (IZhO17_road)C++17
52 / 100
411 ms900 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;
    assert(n <= 5000);

    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<pair<int, int>> depths;
    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++;
                if (p == -1) depths.push_back(ts);
                comb(cur, ts);
            }
        }
        return cur;
    };

    pair<ll, ll> ans{0, 1};
    for (int i = 0; i < n; i++) {
        depths.clear();
        dfs(i, -1, dfs);
        sort(depths.rbegin(), depths.rend());

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

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