제출 #960630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
960630		Turkhuu	Hard route (IZhO17_road)	C++17	100 / 100	628 ms	179280 KiB

road

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = -1e9;
struct S {
    int mx, fq;
    S() : mx(inf), fq(0) {}
    S(int v, int c) : mx(v), fq(c) {}
};
S f(const S &a, const S &b) {
    if (a.mx > b.mx) return a;
    if (b.mx > a.mx) return b;
    return S(a.mx, a.fq + b.fq);
}
S g(S a) {
    a.mx++;
    return a;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<int>> adj(N), ch(N);
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<S> dp(N), pd(N);
    function<void(int, int)> dfs = [&](int x, int p) {
        if (x && adj[x].size() == 1) {
            dp[x] = S(0, 1);
            return;
        }
        for (int y : adj[x]){ 
            if (y == p) continue;
            dfs(y, x);
            dp[x] = f(dp[x], g(dp[y]));
            ch[x].push_back(y);
        }
    };
    dfs(0, -1);
    ll ans = 0, cnt = 1;
    function<void(int)> rer = [&](int x) {
        if (adj[x].size() > 2) {
            vector<S> a{g(pd[x])};
            for (int y : ch[x]) a.push_back(g(dp[y]));
            sort(a.begin(), a.end(), [&](auto &s, auto &t) {
                return s.mx > t.mx;
            });
            ll v = 1LL * a[0].mx * (a[1].mx + a[2].mx), c = 0;
            if (a[1].mx == a[2].mx) {
                for (auto &s : a) if (s.mx == a[1].mx) c += s.fq;
                c *= c;
                for (auto &s : a) if (s.mx == a[1].mx) c -= 1LL * s.fq * s.fq;
                c /= 2;
            } else {
                int c1 = 0, c2 = 0;
                for (auto &s : a) {
                    if (s.mx == a[1].mx) c1 += s.fq;
                    if (s.mx == a[2].mx) c2 += s.fq;
                }
                c = 1LL * c1 * c2;
            }
            if (v > ans) ans = v, cnt = c;
            else if (v == ans) cnt += c;
        }
        int K = ch[x].size(); if (K == 0) return;
        vector<S> pre(K + 1), suf(K + 1);
        for (int i = 0; i < K; i++) pre[i + 1] = f(pre[i], dp[ch[x][i]]);
        for (int i = K - 1; i; i--) suf[i - 1] = f(suf[i], dp[ch[x][i]]);
        for (int i = 0; i < K; i++) {
            int y = ch[x][i];
            if (x == 0 && K == 1) pd[y] = S(0, 1);
            else pd[y] = g(f(f(pre[i], suf[i]), pd[x]));
            rer(y);
        }
    };
    rer(0);
    cout << ans << " " << cnt;
    return 6/22;
}

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