Submission #1267403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267403		jaditya	Hard route (IZhO17_road)	C++17	0 / 100	1 ms	2628 KiB

road

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
#define ll long long

using namespace std;

vector<ll> adj[100005];
ll fir[100005] = {0};
ll sec[100005] = {0};
ll ans[100005] = {0};

void dfs(ll u, ll par) {
    for(ll &v: adj[u]) {
        if(v==par)
            continue;
        dfs(v, u);
        if(fir[v] + 1 > fir[u])
        {
            sec[u] = fir[u];
            fir[u] = fir[v] + 1;
        }
        else if(fir[v]+1 > sec[u])
            sec[u] = fir[v] + 1;
    }
    // cout << u << " " << fir[u] << " " << sec[u] << "\n";
}

void dfs2(ll u, ll par, ll to_p) {
    ans[u] = max(sec[u]*(fir[u]+to_p), to_p*(sec[u]+fir[u]));
    
    for(ll &v: adj[u]) {
        if(v==par)
            continue;
        if(fir[v]+1==fir[u])
            dfs2(v, u, max(sec[u], to_p)+1);
        else
            dfs2(v, u, max(fir[u], to_p)+1);
    }
}

pair<ll, ll> solve(ll n, vector<pair<ll, ll>> edges) {
    for(auto &e: edges) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }
    
    dfs(1, -1);
    dfs2(1, -1, 0);
    pair<ll, ll> res = {0, 0};
    for(ll i=1; i<=n; i++)
    {
        if(ans[i]==res.first)
            res.second++;
        else if(ans[i]>res.first)
            res = {ans[i], 1};
    }
    return res;
}

int main() {
    ll n, a, b;
    cin >> n;
    vector<pair<ll, ll>> edges;
    for(ll i=0; i<n-1; i++)
    {
        cin >> a >> b;
        edges.push_back({a, b});
    }
    auto res = solve(n, edges);
    cout << res.first << " " << res.second << "\n";
    return 0;
}

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