Submission #941890

#	Time	Username	Problem	Language	Result	Execution time	Memory
941890		LonlyR	Hard route (IZhO17_road)	C++17	100 / 100	734 ms	229892 KiB

road

#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second

using namespace std;
const int maxn = 5e5 + 5;
int n;
ii res, dp[maxn];
vector<int> adj[maxn];

inline ii upd(ii a, int x, int y)
{
    if (a.ff < x)
        a = {x, y};
    else if (a.ff == x)
        a.ss += y;
    return a;
}

void dfs(int x = 1, int p = 1)
{
    dp[x].ss = 1;
    for (int i : adj[x]) if (i != p)
    {
        dfs(i, x);
        dp[x] = upd(dp[x], dp[i].ff + 1, dp[i].ss);
    }
}

void reroot(int x = 1, int p = 1, ii fp = {0, 1})
{
    vector<ii> pre = {fp}, suf = {{0, 0}}, cand;
    if (x > 1 || adj[x].size() == 1)
        cand.emplace_back(fp);
    for (int i : adj[x]) if (i != p)
        cand.emplace_back(dp[i].ff + 1, dp[i].ss);
    sort(cand.begin(), cand.end(), greater<ii>());
    if (cand.size() >= 3)
    {
        int hardness = cand[0].ff * (cand[1].ff + cand[2].ff), ways = 0, tmp = 0;
        for (auto i : cand) if (i.ff == cand[2].ff) tmp += i.ss;
        if (cand[1].ff == cand[2].ff)
        {
            ways = tmp * tmp;
            for (auto i : cand) if (i.ff == cand[2].ff)
                ways -= i.ss * i.ss;
            ways /= 2;
        }
        else if (cand[0].ff == cand[1].ff)
        {
            ways = (cand[0].ss + cand[1].ss) * tmp;
        } else ways = cand[1].ss * tmp;
        res = upd(res, hardness, ways);
    }
    for (int i : adj[x]) if (i != p) pre.emplace_back(upd(pre.back(), dp[i].ff + 1, dp[i].ss));
    for (int j = (int)adj[x].size() - 1; j >= 0; j--)
    {
        int i = adj[x][j];
        if (i == p) continue;
        suf.emplace_back(upd(suf.back(), dp[i].ff + 1, dp[i].ss));
    }
    reverse(suf.begin(), suf.end());
    int cnt = 0;
    for (int i : adj[x]) if (i != p)
    {
        pre[cnt].ff++;
        ii xx = upd(pre[cnt], suf[cnt + 1].ff + 1, suf[cnt + 1].ss);
        reroot(i, x, xx);
        cnt++;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n;
    for (int i = 1, u, v; i < n; i++)
        cin >> u >> v,
        adj[u].emplace_back(v),
        adj[v].emplace_back(u);
    dfs();
    reroot();
    cout << res.ff << " " << max(1ll, res.ss);
}

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