Submission #290070

#	Time	Username	Problem	Language	Result	Execution time	Memory
290070		apostoldaniel854	Hard route (IZhO17_road)	C++14	0 / 100	8 ms	12160 KiB

road

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
const int N = 5e5;

struct Best {
    ll mx;
    ll freq;
};
vector <int> gr[1 + N];

int n;
Best dpDown[1 + N], dpUp[1 + N];
void updateBest (Best &ans, Best cur) {
    if (cur.freq == 0) return;
    if (ans.mx < cur.mx) {
        ans = cur;
    }
    else if (ans.mx == cur.mx)
        ans.freq += cur.freq;
}

void dfsDown (int node, int par) {
    dpDown[node] = {0, 1};
    for (int son : gr[node])
        if (son != par) {
            dfsDown (son, node);
            updateBest (dpDown[node], {dpDown[son].mx + 1, dpDown[son].freq});
        }
}

Best pref[1 + N], suff[1 + N];

void dfsUp (int node, int par) {
    int sz = gr[node].size ();
    for (int i = 0; i < sz; i++) {
        int son = gr[node][i];
        pref[i] = {0, 0};
        if (i > 0)
            pref[i] = pref[i - 1];
        if (son != par)
            updateBest (pref[i], {dpDown[son].mx + 2, dpDown[son].freq});
    }
    for (int i = sz - 1; i >= 0; i--) {
        int son = gr[node][i];
        suff[i] = {0, 0};
        if (i < sz - 1)
            suff[i] = suff[i + 1];
        if (son != par)
            updateBest (suff[i], {dpDown[son].mx + 2, dpDown[son].freq});
    }
    for (int i = 0; i < sz; i++) {
        int son = gr[node][i];
        if (son != par) {
            updateBest (dpUp[son], {dpUp[node].mx + 1, dpUp[node].freq});
            if (i > 0)
                updateBest (dpUp[son], pref[i - 1]);
            if (i < sz - 1)
                updateBest (dpUp[son], suff[i + 1]);
            dfsUp (son, node);
        }
    }
}
bool cmp (Best a, Best b) {
    return a.mx > b.mx;
}

struct Help {
    ll mx;
    ll freq;
    ll cnt;
};
ll dp[3];
Best ans;
void solve (int node, int par) {
    vector <Best> edges;
    for (int son : gr[node])
        if (son != par)
            edges.pb ({dpDown[son].mx + 1, dpDown[son].freq});
    if (dpUp[node].mx > 0)
        edges.pb (dpUp[node]);

    sort (edges.begin (), edges.end (), cmp);
    while (edges.size () >= 3 && edges.back ().mx < edges[2].mx)
        edges.pop_back ();

    if (edges.size () >= 3) {
        map <int, vector <int>> mp;
        for (Best edge : edges)
            mp[edge.mx].pb (edge.freq);
        vector <Help> good;
        assert (mp.size () <= 3);
        for (auto x : mp) {
            ll sum = 0;
            for (ll y : x.second)
                sum += y;
            good.pb ({x.first, sum, (int) x.second.size ()});
        }
        reverse (good.begin (), good.end ());
        if (good.size () == 1) {
            dp[1] = dp[2] = 0;
            for (Best edge : edges) {
                ll dp1 = dp[1] + edge.freq;
                ll dp2 = dp[2] + dp[1] * edge.freq;
                dp[1] = dp1; dp[2] = dp2;
            }
            updateBest (ans, {2 * good[0].mx * good[0].mx, dp[2]});
        }
        else if (good.size () == 2) {
            if (good[0].cnt > 1)
                updateBest (ans, {good[0].mx * (good[0].mx + good[1].mx), good[0].freq * good[1].freq});
            else {
                dp[1] = dp[2] = 0;
                for (Best edge : edges) {
                    if (edge.mx == good[1].mx) {
                        ll dp1 = dp[1] + edge.freq;
                        ll dp2 = dp[2] + dp[1] * edge.freq;
                        dp[1] = dp1; dp[2] = dp2;
                    }
                }
                updateBest (ans, {2 * good[0].mx * good[1].mx, dp[2]});
            }
        }
        else {
            updateBest (ans, {good[0].mx * (good[1].mx + good[2].mx), good[1].freq * good[2].freq});
        }
    }
    for (int son : gr[node])
        if (son != par)
            solve (son, node);
}

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

    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        gr[x].pb (y);
        gr[y].pb (x);
    }
    int root = 0;
    for (int i = 1; i <= n; i++)
        if (gr[i].size () > 1)
            root = i;
    ans = {0, 1};
    if (root) {
        dfsDown (root, 0);
        dpUp[root] = {-n, 0};
        dfsUp (root, 0);
        solve (root, 0);
    }
    cout << ans.mx << " " << ans.freq;
    return 0;
}

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