IPST58: Bypass

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int N = 1e5 + 5;

vector<pii> edges;
vector<int> adj[N];
int subTree[N], par[N];
tiii mx[N];

void DFS(int u, int p){
    par[u] = p;
    int cnt = 1;
    int idx = 0;
    int fMx = 0;
    int sMx = 0;
    for(int v : adj[u]){
        if(v == p){
            continue;
        }
        DFS(v, u);
        cnt += subTree[v];
        if(subTree[v] > fMx){
            sMx = fMx;
            fMx = subTree[v];
            idx = v;
        } else if(subTree[v] > sMx){
            sMx = subTree[v];
        }
    }
    mx[u] = tiii(fMx, idx, sMx);
    subTree[u] = cnt;
}

int main(){

    int nVertex;
    scanf("%d", &nVertex);
    for(int i = 1; i < nVertex; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges.emplace_back(u, v);
    }
    DFS(1, 0);
    lli ans = 0;
    for(pii e : edges){
        int u = e.first;
        int v = e.second;
        int mxU = par[u] == v ? 0 : nVertex - subTree[u];
        mxU = max(mxU, get<1>(mx[u]) == v ? get<2>(mx[u]) : get<0>(mx[u]));
        int mxV = par[v] == u ? 0 : nVertex - subTree[v];
        mxV = max(mxV, get<1>(mx[v]) == u ? get<2>(mx[v]) : get<0>(mx[v]));
        ans = max(ans, (lli)mxU * mxV);
    }
    cout << ans;

    return 0;
}