Submission #1263295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263295		tubication	Hard route (IZhO17_road)	C++20	100 / 100	426 ms	222704 KiB

road

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define synchronize {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false); debug("%s time : %.4fs", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))

#define ll long long
#define ld long double
#define ull unsigned long long

#define pii pair <int, int>
#define pli pair <ll, int>
#define pil pair <int, ll>
#define pll pair <ll, ll>

#define vvi vector <vector <int>>

#define all(v) (v).begin(), (v).end()
#define __builtin_popcount __builtin_popcountll

#define fi first
#define se second

template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        }
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        }
        return false;
    }   

const int nmax = 5e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = (ll)1e18;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r) {
    return uniform_int_distribution <long long>(l, r)(rng);
}

/** END OF TEMPLATE **/

int n, u, v;
vector <int> adj[nmax];
pll res = {-1, -1};

pii f[nmax], g[nmax];

void dfs1(int u, int p) {
    f[u] = {0, 1};

    for (int v: adj[u]) {
        if (v == p) continue;
        dfs1(v, u);

        if (f[u].fi < f[v].fi + 1) {
            f[u].fi = f[v].fi + 1;
            f[u].se = f[v].se;
        }
        else if (f[u].fi == f[v].fi + 1) f[u].se += f[v].se;
    }
}

void dfs2(int u, int p) {
    vector <pii> tmp;
    multiset <int> st;
    map <int, int> mp;

    tmp.emplace_back(g[u].fi, g[u].se);
    for (int v : adj[u]) {
        if (v == p) continue;

        tmp.emplace_back(f[v].fi + 1, f[v].se);
        st.insert(f[v].fi + 1);
        mp[f[v].fi + 1] += f[v].se;
    }

    sort(all(tmp), [] (pii a, pii b) { return a.fi > b.fi; });

    if (adj[u].size() >= 3) {
        ll w = 1ll * (tmp[0].fi) * (tmp[1].fi + tmp[2].fi);
        pll cnt = {0, 0};
        
        for (pll x : tmp) {
            if (x.fi == tmp[2].fi) cnt.fi += x.se * cnt.se;
            if (x.fi == tmp[1].fi) cnt.se += x.se;
        }

        if (w > res.fi) res = {w, cnt.fi};
        else if (w == res.fi) res.se += cnt.fi;
    }
    
    for (int v : adj[u]) {
        if (v == p) continue;
        
        st.erase(st.find(f[v].fi + 1));
        mp[f[v].fi + 1] -= f[v].se;

        if (st.empty()) g[v] = {g[u].fi + 1, g[u].se};
        else {
            if (g[u].fi > *st.rbegin()) g[v] = {g[u].fi + 1, g[u].se};
            else if (*st.rbegin() > g[u].fi) g[v] = {*st.rbegin() + 1, mp[*st.rbegin()]};
            else g[v] = {g[u].fi + 1, mp[*st.begin()] + g[u].se};
        }

        dfs2(v, u);
        st.insert(f[v].fi + 1);
        mp[f[v].fi + 1] += f[v].se;
    }
}

int main() {
    synchronize;

    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    if (n == 2) {
        cout << "0 1";
        return 0;
    }

    int r = -1;
    for (int u = 1; u <= n; u++) {
        if (adj[u].size() > 1) { r = u; break; }
    }

    dfs1(r, -1);
    dfs2(r, -1);

    if (res.fi == -1) res = {0, 1};
    cout << res.fi << ' ' << res.se;

    return 0;
}

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