Submission #1116895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116895		kfhjad	Hard route (IZhO17_road)	C++17	100 / 100	588 ms	148552 KiB

road

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<int> adj[500001];
int up[500001], down[500001];
ll upFreq[500001], downFreq[500001];
ll ans = 0;
ll freq = 1;

void update(ll x, ll f)
{
    if (x > ans)
        ans = x, freq = f;
    else if (x == ans)
        freq += f;
}

void dfs(int node, int p)
{
    downFreq[node] = upFreq[node] = 1;
    
    for (int i : adj[node])
    {
        if (i == p)
            continue;
        
        dfs(i, node);
        
        if (down[node] < down[i] + 1)
            down[node] = down[i] + 1, downFreq[node] = downFreq[i];
        else if (down[node] == down[i] + 1)
            downFreq[node] += downFreq[i];
    }
}

void dfs1(int node, int p)
{
    vector<array<ll, 2>> paths;
    paths.push_back({up[node], upFreq[node]});
    
    for (int i : adj[node])
        if (i != p)
            paths.push_back({down[i] + 1, downFreq[i]});

    sort(paths.rbegin(), paths.rend());

    if (adj[node].size() > 2)
    {
        ll a = paths[0][0];
        ll b = paths[1][0];
        ll c = paths[2][0];
        ll x = a * (b + c);

        // all distinct
        if (a != b && b != c)
        {
            ll cnt = 0;
            for (auto [len, f] : paths)
                if (len == c)
                    cnt += f;
            
            update(x, paths[1][1] * cnt);
        }
        else if (a == b && b == c) // all same
        {
            ll cnt = 0;
            ll res = 0;
            for (auto [len, f] : paths)
                if (len == c)
                    cnt += f;
            
            // if (node == 2)
            //     cout << "HI " << cnt << endl;
                    
            for (auto [len, f] : paths)
                if (len == c)
                    res += f * (cnt - f);
            
            update(x, res / 2);
        }
        else if (a == b) // only first two are the same
        {
            ll cnt = 0;
            for (auto [len, f] : paths)
                if (len == c)
                    cnt += f;
            
            update(x, (paths[0][1] + paths[1][1]) * cnt);
        }
        else if (b == c) // last two are the same
        {
            ll cnt = 0;
            ll res = 0;
            for (auto [len, f] : paths)
                if (len == c)
                    cnt += f;
                    
            for (auto [len, f] : paths)
                if (len == c)
                    res += f * (cnt - f);         
            
            update(x, res / 2);
        }
    }
    
    ll best1 = 0, best2 = 0;
    
    for (auto [len, f] : paths)
        if (len == paths[0][0])
            best1 += f;
    
    for (auto [len, f] : paths)
        if (len == paths[1][0])
            best2 += f;

    for (int i : adj[node])
    {
        if (i == p)
            continue;
        
        ll path = down[i] + 1;
        
        if (path == paths[0][0])
        {
            best1 -= downFreq[i];
            
            if (best1 == 0) // only 1 longest path
                up[i] = paths[1][0] + 1, upFreq[i] = best2;
            else
                up[i] = paths[0][0] + 1, upFreq[i] = best1;
        }
        else
            up[i] = paths[0][0] + 1, upFreq[i] = best1;
            
        dfs1(i, node);
    }
}

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
    int N;
    cin >> N;
    
    while (--N)    
    {
        int a, b;
        cin >> a >> b;
        
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    dfs(1, 0);
    dfs1(1, 0);
    
    cout << ans << ' ' << freq << endl;
	
    return 0;
}

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