제출 #960629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
960629		Turkhuu	Hard route (IZhO17_road)	C++17	52 / 100	2041 ms	66504 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);
    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);
    function<void(int, int)> dfs = [&](int x, int p) {
        if (p != -1 && 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]));
        }
    };
    dfs(0, -1);
    ll ans = 0, cnt = 1;
    for (int r = 0; r < N; r++) {
        if (adj[r].size() <= 2) continue;
        dp = vector<S>(N);
        dfs(r, -1);
        vector<S> a;
        for (int y : adj[r]) 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;
    }
    cout << ans << " " << cnt;
    return 6/22;
}

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