Submission #1131786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131786		birsnot	Hard route (IZhO17_road)	C++20	100 / 100	584 ms	210860 KiB

road

// author: Nardos Wehabe

#include "bits/stdc++.h"


#ifndef ONLINE_JUDGE
#include "./debug/debug.h"
#endif

using namespace std;
typedef long long ll;
typedef map<int, int, greater<>> mapg;
// typedef __int128 lll;

void chmx(int n, int& mx1, int& mx2) {
    if (n > mx1) {
        mx2 = mx1;
        mx1 = n;
    } else mx2 = max(n, mx2);
}

void chmx2(int n, int& mx1, int& mx2, int& mx3) {
    if (n > mx1) {
        mx3 = mx2;
        mx2 = mx1;
        mx1 = n;
    } else chmx(n, mx2, mx3);
}

void convert3(mapg& cnts, array<array<int, 2>, 3>& cur) {
    int i = 0;
    for (auto& [n, fq] : cnts) {
        cur[i++] = { n, fq };
        if (i >= 3) return;
    }
}
void convert6(mapg& cnts, array<array<int, 2>, 6>& cur) {
    int i = 0;
    for (auto& [n, fq] : cnts) {
        cur[i++] = { n, fq };
        if (i >= 6) return;
    }
}

void incr(array<array<int, 2>, 3>& cur) {
    cur[0][0]++;
    cur[0][1] += cur[0][0] == 1;
    cur[1][0] += cur[1][0] != 0;
    cur[2][0] += cur[2][0] != 0;
}

void solve() {
    int N;
    cin >> N;
    vector<int> adj[N];
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }

    vector<array<array<int, 2>, 3>> mxs(N, { {0, 0} });

    function<array<array<int, 2>, 3>(int, int)> dfs1 = [&](int v, int p) {
        mapg cnts;
        for (auto ch : adj[v]) {
            if (ch == p) continue;
            auto ret = dfs1(ch, v);
            for (auto [n, fq] : ret) cnts[n] += fq;
        }
        convert3(cnts, mxs[v]);
        incr(mxs[v]);
        return mxs[v];
        };
    dfs1(0, -1);


    vector<array<ll, 2>> ans(N, { 0 });

    ll best = 0;

    function<void(int, int, array<array<int, 2>, 3>&)> dfs2 = [&](int v, int p, array<array<int, 2>, 3>& fr_p) {
        array<array<int, 2>, 6> cur{ {0, 0} };
        {
            mapg cnts;
            if (p != -1) mxs[p] = fr_p;

            int mx1 = 0, mx2 = 0, mx3 = 0;
            for (auto ch : adj[v]) {
                auto ret = mxs[ch];
                chmx2(ret[0][0], mx1, mx2, mx3);
                for (auto [n, fq] : ret) cnts[n] += fq;
            }
            convert6(cnts, cur);
            int cnt1 = cnts[mx1], cnt2 = cnts[mx2], cnt3 = cnts[mx3];
            ans[v][0] = (1ll * (mx2 + mx3) * mx1) * (mx3 > 0);
            best = max(ans[v][0], best);

            if (mx2 == mx3) {
                ans[v][1] = 1ll * cnt2 * (cnt2 - 1) / 2;

                for (auto ch : adj[v]) {
                    auto ret = mxs[ch];
                    int fq = 0;
                    for (auto [n, f] : ret) {
                        fq += f * (n == mx2);
                    }
                    if (ret[0][0] == mx1 && ret[0][1] == cnt1) {
                        ans[v][1] -= 1ll * fq * (cnt2 - fq);
                    }
                    ans[v][1] -= 1ll * fq * (fq - 1) / 2;
                }
            } else {
                ans[v][1] = 1ll * cnt2 * cnt3;
                for (auto ch : adj[v]) {
                    auto ret = mxs[ch];
                    int fq1 = 0, fq2 = 0;
                    for (auto [n, fq] : ret) {
                        fq1 += fq * (n == mx2);
                        fq2 += fq * (n == mx3);
                    }
                    if (ret[0][0] == mx1 && ret[0][1] == cnt1) {
                        ans[v][1] -= 1ll * fq1 * (cnt3 - fq2) + 1ll * fq2 * (cnt2 - fq1);
                    }
                    ans[v][1] -= 1ll * fq1 * fq2;
                }
            }
        }
        for (auto ch : adj[v]) {
            if (ch == p) continue;
            auto [n1, n2, n3] = mxs[ch];
            array<array<int, 2>, 3> to_ch = { {0, 0} };
            int j = 0;
            for (int i = 0; i < 6; ++i) {
                int n = cur[i][0], fq = cur[i][1];
                fq -= n1[1] * (n1[0] == n) + n2[1] * (n == n2[0]) + n3[1] * (n == n3[0]);
                if (fq) {
                    to_ch[j++] = { n, fq };
                }
                if (j >= 3) break;
            }
            incr(to_ch);
            dfs2(ch, v, to_ch);
        }
        };
    array<array<int, 2>, 3> ne = { {0, 0} };
    dfs2(0, -1, ne);

    if (best == 0) {
        cout << "0 1\n";
        return;
    }
    ll cnt = 0;
    for (auto [v, fq] : ans) {
        if (v == best) cnt += fq;
        assert(fq >= 0);
    }
    cout << best << " " << cnt << "\n";
}

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

    int tt = 1;
    // cin >> tt;

    while (tt--)
        solve();
}

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 48 / 48