ข้อนี้แท้จริงแล้วโจทย์ต้องการให้เราหาคู่เมือง $u$ และ $v$ ที่ จำนวนเมืองที่ต้องผ่าน $u$ ถึงจะไป $v$ ได้ คูณกับ จำนวนเมืองที่ต้องผ่าน $v$ ถึงจะไป $u$ ได้ มีค่ามากที่สุด

Key ของข้อนี้คือคู่เมือง $u$ และ $v$ ที่ดีที่สุดจะอยู่ห่างกัน 2 step เท่านั้น เนื่องจาก หากมันอยู่ห่างกันมากกว่านี้เราสามารถขยับ $u$ เข้าไปใกล้ขึ้นได้ และ คำตอบจะดีขึ้นเสมอ

เราจะแก้โจทย์นี้ในต้นไม้ที่ root ที่เมือง $1$ โดยนิยามใหั $size_i$ เป็น ขนาดของ subtree ของ $i$

สำหรับเมือง $x$ ใดๆ เราจะสนใจแค่เมือง $y$ ที่มีทางเชื่อมกับ $x$ เท่านั้น โดย

1. $y$ เป็นลูกของ $x$: จำนวนเมืองที่ต้องผ่าน $y$ จะเท่ากับ $size_y$
2. $y$ เป็นพ่อของ $x$: จำนวนเมืองที่ต้องผ่าน $y$ จะเท่ากับ $n - size_x$

ในบรรดาเมือง $y$ เหล่านี้ เราจะสนใจแค่ค่าสองอันดับที่มากที่สุดและนำมาคูณกัน

Time-complexity: $\mathcal{O}(N)$

void solve(int u, int par) {
  sz[u] = 1;
  for(auto v : adj[u]) {
    if(v == par) continue;
    solve(v, u);
    sz[u] += sz[v];
  }
  
  int mx[2] = {-1, -1};
  for(auto v : adj[u]) {
    int val;
    if(v == par) val = n - sz[u];
    else val = sz[v];
    
    if(val > mx[0]) swap(mx[0], val);
    if(val > mx[1]) swap(mx[1], val);
  }
  
  if(mx[0] != -1 && mx[1] != -1) {
      ans = max(ans, (long long)mx[0] * mx[1]);
  }
}