Submission #1281688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281688		hxian	Hard route (IZhO17_road)	C++20	100 / 100	489 ms	121256 KiB

road

// dmoj problem: https://vjudge.net/contest/757167#problem/K
#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;

int n, out, amnt;
pair<int, int> dist[500001];
vector<int> adjList[500001];
void dfs(int node, int last)
{
    dist[node] = {0, 1};
    for (int u : adjList[node])
    {
        if (u != last)
        {
            dfs(u, node);
            if (dist[u].first + 1 > dist[node].first)
                dist[node] = {dist[u].first + 1, dist[u].second};
            else if (dist[u].first + 1 == dist[node].first)
                dist[node].second += dist[u].second;
        }
    }
}
void reroot(int node, int last, int before, int waysbefore)
{
    vector<pair<int, int>> options;
    if (before != 0)
        options.push_back({before, waysbefore});
    for (int u : adjList[node])
        if (u != last)
            options.push_back({dist[u].first + 1, dist[u].second});
    sort(options.begin(), options.end());
    if (options.size() == 1)
    {
        if (out == 0)
            amnt += waysbefore;
        // this will overcount x2
    }
    if (options.size() == 2)
    {
    } // overcount
    if (options.size() >= 3)
    {
        int candout = options[options.size() - 1].first * (options[options.size() - 2].first + options[options.size() - 3].first);
        if (candout > out)
        {
            out = candout;
            amnt = 0;
        }
        if (candout == out)
        {
            pair<int, int> want = {-1, -1};
            want.first = options[options.size() - 2].first;
            if (options[options.size() - 3].first != want.first)
                want.second = options[options.size() - 3].first;
            pair<int, int> sums;
            int delta = 0;
            for (int i = 0; i < options.size(); i++)
            {
                if (options[i].first == want.first)
                    sums.first += options[i].second;
                if (options[i].first == want.second)
                    sums.second += options[i].second;
            }
            if (want.second != -1)
                delta += sums.first * sums.second;
            else
            {
                delta += sums.first * sums.first;
                for (int i = 0; i < options.size(); i++)
                    if (options[i].first == want.first)
                        delta -= options[i].second * options[i].second;
                delta /= 2;
            }
            amnt += delta;
        }
    }

    int amntbest = 0;
    int sb = -1;
    int amntsecondbest = 0;
    for (int i = options.size() - 1; i >= 0; i--)
    {
        if (options[i].first == options.back().first)
            amntbest += options[i].second;
        else if (sb == -1)
            sb = options[i].first;
        if (options[i].first == sb)
            amntsecondbest += options[i].second;
    }
    for (int u : adjList[node])
        if (u != last)
        {
            if (dist[u].first + 1 == options.back().first)
            {
                if (amntbest - dist[u].second > 0)
                    reroot(u, node, options.back().first + 1, amntbest - dist[u].second);
                else
                    reroot(u, node, sb + 1, amntsecondbest);
            }
            else
                reroot(u, node, options.back().first + 1, amntbest);
        }
}
int32_t main()
{
    cin.sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        adjList[a].push_back(b);
        adjList[b].push_back(a);
    }
    if (n == 2)
    {
        cout << "0 1" << "\n";
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        if (adjList[i].size() != 1)
        {
            dfs(i, 0);
            reroot(i, 0, 0, 1);
            break;
        }
    }
    cout << out << " ";
    cout << (out == 0 ? amnt / 2 : amnt) << "\n";

    return 0;
}

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