Submission #1131815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131815		birsnot	Hard route (IZhO17_road)	C++20	100 / 100	318 ms	125252 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 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<int> mxh(N), cnts(N);

    function<void(int, int)> dfs1 = [&](int v, int p) {
        for (auto ch : adj[v]) {
            if (ch == p) continue;
            dfs1(ch, v);
            if (mxh[ch] > mxh[v]) {
                mxh[v] = mxh[ch];
                cnts[v] = cnts[ch];
            } else if (mxh[ch] == mxh[v]) cnts[v] += cnts[ch];
        }
        mxh[v]++;
        cnts[v] += mxh[v] == 1;
        };
    dfs1(0, -1);

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

    ll best = 0;

    function<void(int, int, int, int)> dfs2 = [&](int v, int p, int pmx, int pcnt) {
        int mx1 = pmx, mx2 = 0, mx3 = 0;
        int cnt1 = 0, cnt2 = 0, cnt3 = 0;
        {
            vector<array<int, 2>> mxs{ {pmx, pcnt} };
            for (auto ch : adj[v]) {
                if (ch == p) continue;
                mxs.push_back({ mxh[ch], cnts[ch] });
                chmx2(mxh[ch], mx1, mx2, mx3);
            }
            ll decr = 0;
            for (auto [n, fq] : mxs) {
                cnt1 += fq * (n == mx1);
                cnt2 += fq * (n == mx2);
                cnt3 += fq * (n == mx3);
                if(n == mx2) decr += 1ll*fq*(fq - 1)/2;
            }
            ans[v][0] = (1ll * (mx2 + mx3) * mx1) * (mx3 > 0);
            best = max(ans[v][0], best);
            if (best && ans[v][0] == best) {
                if (mx2 == mx3) {
                    ans[v][1] += 1ll * cnt2 * (cnt2 - 1) / 2 - decr;
                } else {
                    ans[v][1] = 1ll * cnt2 * cnt3;
                }
            }
        }
        for (auto ch : adj[v]) {
            if (ch == p) continue;
            int chmx = mx1, chcnt = cnt1;
            if (mxh[ch] == mx1 && cnts[ch] == cnt1) {
                chmx = mx2, chcnt = cnt2;
            } else if (mxh[ch] == mx1) {
                chmx = mx1, chcnt = cnt1 - cnts[ch];
            }
            chmx++;
            chcnt += chmx == 1;
            dfs2(ch, v, chmx, chcnt);
        }
        };
    dfs2(0, -1, 0, 0);


    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