Gọi ~f(u, i)~ là số cặp nhiều nhất khi xét subtree gốc ~u~ và có ~i~ đỉnh có thể đôi một đến được nhau thông qua gốc ~u~.

Xét hai trường hợp:

• Tô ~u~ màu đen:

  • Giả sử đang xét lần lượt các con trực tiếp ~v_1, v_2, ... v_k~ của ~u~.

  • Ta có ~f(u, i + j)~ ~\leftarrow~ ~f(u, i) f(v_x, j) + i \times j~ với ~x~ từ ~1~ đến ~k~. Nghĩa là ở subtree gốc ~u~ có sẵn ~i~ nút mà đường đi nó từ gốc ~u~ không chứa đỉnh trắng nào trừ nút xuất phát, ghép cặp cùng với ~j~ nút như vậy ở subtree gốc ~v_x~, và chúng phải đi qua gốc ~u~ màu đen.

• Tô ~u~ màu trắng: ~f(u, 1) \leftarrow \sum_{v \in adj(u)} max_i(f(v, i) + i)~ do ta chỉ có thể đi thẳng từ ~v'~ thuộc subtree gốc ~v~ đến ~u~ mà không thể đi vòng qua ~u~ để đến một đỉnh ~v'~ ở một subtree khác

Nhận thấy ~i \leq sub_u~ với ~sub_u~ là số đỉnh trong cây con gốc ~u \rightarrow~ tối ưu bằng knapsack on tree. Độ phức tạp: ~O(n^2)~

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

const int N = 5005;

void maximize (int& a, int b) {
  a = max(a, b);
}

int dp[N][N];
int child[N];
vector <int> g[N];
int n;

void dfs (int u, int par = -1) {
  child[u] = 1;
  dp[u][0] = 0;
  int tot_dp_child = 0;

  for (int v : g[u]) {
    if (v == par) continue;
    dfs(v, u);
    for (int i = child[u]; i >= 0; i--)
      for (int j = child[v]; j >= 0; j--) {
        if (i + j <= n) maximize(dp[u][i + j], dp[u][i] + dp[v][j] + i * j);
      }
    child[u] += child[v];
    int best_v = 0;
    for (int i = 0; i <= child[v]; i++)
      maximize(best_v, dp[v][i] + i);
    tot_dp_child += best_v;
  }

  maximize(dp[u][1], tot_dp_child);
}

void sol() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    g[i].clear();
  }

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

  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= n; j++)
      dp[i][j] = -1e9;

  dfs(1);

  int best = 0;
  for (int i = 0; i <= n; i++)
    best = max(best, dp[1][i]);

  cout << best << "\n";
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int tt;
  cin >> tt;

  while (tt--)
    sol();

  return 0;
}