Submission #1316761

#TimeUsernameProblemLanguageResultExecution timeMemory
1316761iamhereforfunHard route (IZhO17_road)C++20
0 / 100
2 ms332 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))
#define int long long

const int N = 5e5 + 5;
const int M = 1e3 + 5;
const int LG = 60;
const int C = 26;
const long long INF = 2e9 + 5;
const int B = 400;
const int MOD = 1e9 + 7;

int n, m;
vector<int> adj[N];
long long ans, mx[N], cnt, up[N], num[N];

void dfs1(int c, int p)
{
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        dfs1(i, c);
        mx[c] = max(mx[c], mx[i] + 1);
    }
}

void add(int &i, int j, int &z, int a)
{
    if (i < j)
    {
        z = a;
        i = j;
    }
    else if (i == j)
    {
        z += a;
    }
}

void dfs2(int c, int p)
{
    vector<int> v;
    map<int, int> mp;
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        mp[mx[i] + 1]++;
        v.push_back(mx[i] + 1);
        up[i] = max(up[i], up[c] + 1);
        num[i] = 1;
    }
    mp[up[c]] += num[c];
    v.push_back(up[c]);
    sort(v.rbegin(), v.rend());
    if (v.size() > 2)
    {
        if (ans < v[0] * (v[1] + v[2]))
        {
            ans = v[0] * (v[1] + v[2]);
            cnt = 0;
        }
        if (ans <= v[0] * (v[1] + v[2]))
        {
            // cout << ans << " " << cnt << "\n";
            // cout << mp[v[1]] << "\n";
            if (v[1] == v[2])
            {
                cnt += mp[v[1]] * (mp[v[2]] - 1) / 2;
            }
            else
            {
                cnt += mp[v[1]] * mp[v[2]];
            }
            // cout << ans << " " << cnt << "\n";
        }
    }
    int cmx = -1, a = 0;
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        add(up[i], cmx + 2, num[i], a);
        add(cmx, mx[i], a, 1);
    }
    reverse(adj[c].begin(), adj[c].end());
    cmx = -1;
    a = 0;
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        add(up[i], cmx + 2, num[i], a);
        add(cmx, mx[i], a, 1);
    }
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        dfs2(i, c);
    }
}

inline void solve()
{
    cin >> n;
    for (int x = 0; x < n - 1; x++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    m = 0;
    for (int x = 1; x <= n; x++)
    {
        if (adj[x].size() == 1)
            m++;
    }
    cnt = ans = 0;
    cnt = m * (m - 1) / 2;
    dfs1(1, 0);
    dfs2(1, 0);
    cout << ans << " " << cnt << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...