Submission #1131632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131632		birsnot	Hard route (IZhO17_road)	C++20	0 / 100	0 ms	328 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 __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 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<int, 6>> mxs(N, { 0 });

    function<array<int, 6>(int, int)> dfs1 = [&](int v, int p) {
        vector<array<int, 2>> cnts;
        for (auto ch : adj[v]) {
            if (ch == p) continue;
            auto [n1, c1, n2, c2, n3, c3] = dfs1(ch, v);
            if (!n1) continue;
            cnts.push_back({ n1, c1 });
            if (!n2) continue;
            cnts.push_back({ n2, c2 });
            if (!n3) continue;
            cnts.push_back({ n3, c3 });
        }
        sort(cnts.begin(), cnts.end(), [](const array<int, 2>& lhs, const array<int, 2>& rhs) {
            return lhs[0] > rhs[0];
            });
        int j = 0, i = 0, L = cnts.size();
        while (i < L && j < 3) {
            int n = cnts[i][0], fq = cnts[i++][1];
            while (i < L && cnts[i][0] == n) {
                fq += cnts[i++][1];
            }
            mxs[v][2 * j] = n;
            mxs[v][2 * j + 1] = fq;
            j++;
        }
        auto& ret = mxs[v];
        ret[0]++;
        ret[1] += adj[v].size() == 1;
        ret[2] += ret[2] != 0;
        ret[4] += ret[4] != 0;
        return ret;
        };

    dfs1(0, -1);

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

    ll best = 0;

    function<void(int, int, array<int, 6>&)> dfs2 = [&](int v, int p, array<int, 6>& fr_p) {
        array<int, 12> cur{ 0 };
        {
            vector<array<int, 2>> cnts;
            auto [n1, c1, n2, c2, n3, c3] = fr_p;
            if (n1) cnts.push_back({ n1, c1 });
            if (n2) cnts.push_back({ n2, c2 });
            if (n3) cnts.push_back({ n3, c3 });
            int mx1 = n1, mx2 = 0, mx3 = 0;
            for (auto ch : adj[v]) {
                if (ch == p) continue;
                auto [n1, c1, n2, c2, n3, c3] = mxs[ch];
                chmx2(n1, mx1, mx2, mx3);
                if (!n1) continue; cnts.push_back({ n1, c1 });
                if (!n2) continue; cnts.push_back({ n2, c2 });
                if (!n3) continue; cnts.push_back({ n3, c3 });
            }
            sort(cnts.begin(), cnts.end(), [](const array<int, 2>& lhs, const array<int, 2>& rhs) {
                return lhs[0] > rhs[0];
                });
            int cnt1 = 0, cnt2 = 0, cnt3 = 0;
            int i = 0, j = 0, L = cnts.size();
            while (i < L) {
                int n = cnts[i][0], fq = cnts[i++][1];
                while (i < L && cnts[i][0] == n) {
                    fq += cnts[i++][1];
                }
                cnt1 += fq * (n == mx1);
                cnt2 += fq * (n == mx2);
                cnt3 += fq * (n == mx3);
                if(j < 6){
                    cur[j * 2] = n;
                    cur[j * 2 + 1] = fq;
                    j++;
                }
            }
            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;
                if (n1 == mx2) {
                    ans[v][1] -= 1ll * c1 * (c1 - 1) / 2;
                }
                else if (n2 == mx2) {
                    ans[v][1] -= 1ll * c2 * (c2 - 1) / 2;
                }
                else if (n3 == mx2) {
                    ans[v][1] -= 1ll * c3 * (c3 - 1) / 2;
                }
                for (auto ch : adj[v]) {
                    if (ch == p) continue;
                    auto [n1, c1, n2, c2, n3, c3] = mxs[ch];
                    if (n1 == mx2) {
                        ans[v][1] -= 1ll * c1 * (c1 - 1) / 2;
                        continue;
                    }
                    if (n2 == mx2) {
                        ans[v][1] -= 1ll * c2 * (c2 - 1) / 2;
                        continue;
                    }
                    if (n3 == mx2) {
                        ans[v][1] -= 1ll * c3 * (c3 - 1) / 2;
                    }
                }
            } else {
                ans[v][1] = 1ll * cnt2 * cnt3;
                int fq1 = c1 * (n1 == mx2) + c2 * (n2 == mx2) + c3 * (n3 == mx2);
                int fq2 = c1 * (n1 == mx3) + c2 * (n2 == mx3) + c3 * (n3 == mx3);
                ans[v][1] -= 1ll * fq1 * fq2;
                for (auto ch : adj[v]) {
                    if (ch == p) continue;
                    auto [n1, c1, n2, c2, n3, c3] = mxs[ch];
                    int fq1 = c1 * (n1 == mx2) + c2 * (n2 == mx2) + c3 * (n3 == mx2);
                    int fq2 = c1 * (n1 == mx3) + c2 * (n2 == mx3) + c3 * (n3 == mx3);
                    ans[v][1] -= 1ll * fq1 * fq2;
                }
            }
        }
        for (auto ch : adj[v]) {
            if (ch == p) continue;
            array<int, 6> to_ch{ 0 };
            auto [n1, c1, n2, c2, n3, c3] = mxs[ch];
            int j = 0;
            for (int i = 0; i < 6; ++i) {
                int n = cur[2 * i], fq = cur[2 * i + 1];
                fq -= c1 * (n1 == n) + c2 * (n == n2) + c3 * (n == n3);
                if (fq) {
                    to_ch[2 * j] = n;
                    to_ch[2 * j + 1] = fq;
                    j++;
                }
                if (j >= 3) break;
            }
            to_ch[0]++;
            to_ch[1] += (to_ch[0] == 1);
            to_ch[2] += to_ch[2] != 0;
            to_ch[4] += to_ch[4] != 0;
            dfs2(ch, v, to_ch);
        }
        };
    array<int, 6> ne = { 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: 0 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48