Submission #1305419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305419		LucasLe	Hard route (IZhO17_road)	C++20	100 / 100	437 ms	170140 KiB

road

#include <bits/stdc++.h>

const int maxn = 5e5 + 5;

long long mx_len, ways;
int N, x, y, z;
std::vector<int> G[maxn + 5];

std::pair<int, int> f[maxn + 5][3];
int cnt[maxn + 5][3];

void preDFS(int u, int p) {
    int &cnt1 = cnt[u][0], &cnt2 = cnt[u][1], &cnt3 = cnt[u][2];
    std::pair<int, int> &pf = f[u][0], &ps = f[u][1], &pt = f[u][2];

    if (p && G[u].size() == 1) {
        cnt1 = 1;
        pf = {0, 1};
        G[u].clear();
        return;
    }

    std::vector<int> tmp;

    for (int v : G[u]) {
        if (v == p) continue;
        preDFS(v, u);
        tmp.push_back(v);
        std::tie(x, y) = f[v][0];
        x++;

        if (x > pf.first) {
            std::swap(cnt2, cnt3);
            pt = ps;
            std::swap(cnt1, cnt2);
            ps = pf;
            cnt1 = 1;
            pf = {x, y};
        } else if (x == pf.first) {
            cnt1++;
            pf.second += y;
        } else if (x > ps.first) {
            std::swap(cnt2, cnt3);
            pt = ps;
            cnt2 = 1;
            ps = {x, y};
        } else if (x == ps.first) {
            cnt2++;
            ps.second += y;
        } else if (x > pt.first) {
            cnt3 = 1;
            pt = {x, y};
        } else if (x == pt.first) {
            cnt3++;
            pt.second += y;
        }
    }

    std::swap(G[u], tmp);
}

void DFS(int u, int p, std::pair<int, int> tmp) {

    int cnt1 = cnt[u][0], cnt2 = cnt[u][1], cnt3 = cnt[u][2];
    std::pair<int, int> pf = f[u][0], ps = f[u][1], pt = f[u][2];

    if (p) {
        std::tie(x, y) = tmp;

        if (x > pf.first) {

            std::swap(cnt2, cnt3);
            pt = ps;

            std::swap(cnt1, cnt2);
            ps = pf;
            cnt1 = 1;
            pf = {x, y};
        } else if (x == pf.first) {
            cnt1++;
            pf.second += y;
        } else if (x > ps.first) {
            std::swap(cnt2, cnt3);
            pt = ps;
            cnt2 = 1;
            ps = {x, y};
        } else if (x == ps.first) {
            cnt2++;
            ps.second += y;
        } else if (x > pt.first) {
            cnt3 = 1;
            pt = {x, y};
        } else if (x == pt.first) {
            cnt3++;
            pt.second += y;
        }
    }

    // 2 4 6 7

    // if (u == 2) {
    //     std::cerr << "? " << pf.first << ' ' << pf.second << ' ' << ps.first << ' ' << ps.second << ' ' << f[u][0].first << '\n';
    // }

    // std::cerr << u << ' ' << cnt1 << ' ' << cnt2 << ' ' << cnt3 << '\n';

    if (cnt1 >= 3) {
        x = pf.first;
        long long len = 1ll * (x + x) * x, num = 0;

        for (int v : G[u]) {
            if (v == p) continue;
            std::tie(x, y) = f[v][0];
            x++;

            if (x == pf.first) {
                num += 1ll * y * (pf.second - y);
            }
        }

        if (tmp.first == pf.first) {
            num += 1ll * tmp.second * (pf.second - tmp.second);
        }

        if (len > mx_len) {
            mx_len = len;
            ways = num;
        } else if (len == mx_len) {
            ways += num;
        }
    } else if (cnt1 == 2 && cnt2 >= 1) {

        x = pf.first;
        y = ps.first;
        long long len = 1ll * (x + y) * x, num = 2ll * pf.second * ps.second;

        if (len > mx_len) {
            mx_len = len;
            ways = num;
        } else if (len == mx_len) {
            ways += num;
        }


        // (x + x) * y = x * y + x * y
        // (x + y) * x = x * x + x * y

    } else if (cnt2 >= 2) {
        // x > y
        x = pf.first;
        y = ps.first;

        long long len = 1ll * (y + y) * x, num = 0;

        for (int v : G[u]) {
            if (v == p) continue;
            std::tie(x, y) = f[v][0];
            x++;

            if (x == ps.first) {
                num += 1ll * y * (ps.second - y);
            }
        }

        if (tmp.first == ps.first) {
            num += 1ll * tmp.second * (ps.second - tmp.second);
        }

        // if (u == 2) {
        //     std::cerr << "@@ " << num << '\n';
        // }

        if (len > mx_len) {
            mx_len = len;
            ways = num;
        } else if (len == mx_len) {
            ways += num;
        }
    
        // (y + y) * x = x * y + x * y;
        // (x + y) * y = y * y + x * y (max)
    } else if (cnt3) {
        // x > y > z
        x = pf.first;
        y = ps.first;
        z = pt.first;

        long long len = 1ll * (y + z) * x, num = 2ll * pt.second * ps.second;
        if (len > mx_len) {
            mx_len = len;
            ways = num;
        } else if (len == mx_len) {
            ways += num;
        }

        // (x + y) * z = x * z + y * z;
        // (x + z) * y = x * y + y * z;
        // (y + z) * x = x * y + x * z; (max)
    }   

    std::vector<std::pair<int, int>> pref, suff;

    pref.push_back({0, 0});
    suff.push_back({0, 0});

    for (int v : G[u]) {
        if (v == p) continue;

        std::tie(x, y) = f[v][0];
        x++;

        if (pref.back().first < x) {
            pref.push_back({x, y});
        } else if (pref.back().first == x) {
            pref.push_back({x, pref.back().second + y});
        } else {
            pref.push_back(pref.back());
        }
    }

    for (int i = G[u].size() - 1; i >= 0; --i) {
        int v = G[u][i];
        if (v == p) continue;

        std::tie(x, y) = f[v][0];
        x++;

        if (suff.back().first < x) {
            suff.push_back({x, y});
        } else if (suff.back().first == x) {
            suff.push_back({x, suff.back().second + y});
        } else {
            suff.push_back(suff.back());
        }
    }
    
    std::pair<int, int> otmp;
    for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if (v == p) continue;

        otmp = tmp;

        std::tie(x, y) = pref[i];

        // if (v == 2 && u == 9) {
        //     std::cerr << "!!! " << i << ' ' << pref[i].first << ' ' << suff[G[u].size() - 1 - i].first << '\n';
        // }

        if (x > tmp.first) {
            tmp = {x, y};
        } else if (x == tmp.first) {
            tmp.second += y;
        }

        std::tie(x, y) = suff[G[u].size() - 1 - i];

        if (x > tmp.first) {
            tmp = {x, y};
        } else if (x == tmp.first) {
            tmp.second += y;
        }

        tmp.first++;
        DFS(v, u, tmp);

        tmp = otmp;
    }
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);

    std::cin >> N;
    for (int i = 1; i < N; ++i) {
        int u, v; std::cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    preDFS(1, 0);
    DFS(1, 0, {0, 1});

    if (!mx_len) {
        std::cout << 0 << ' ' << 1 << '\n';
    } else {
        std::cout << mx_len << ' ' << ways / 2 << '\n';
    }

    return 0;
}

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