考虑答案的下界。
对整棵树进行二分图染色，我们得到答案是 \(n \times (n + 1) - O(n)\) 级别的。但是二分图染色不一定是最优的。
考虑计算 \(O(n)\) 的损失。发现在极大同色连通块内的点对才会造成损失，并且因为损失是 \(O(n)\) 的，所以极大同色连通块大小是 \(O(\sqrt{n})\) 的。
考虑 dp，设 \(f_{u,0/1,i}\) 为包含 \(u\) 的极大颜色为 \(0/1\) 的连通块大小是 \(i\) 的最少损失。转移就按照直接树形背包合并就行。注意我们在 \(v \to u\) 且 \(u,v\) 颜色不同时计算 \(v\) 的连通块的贡献。
本题卡空间，因此需要对于每个 \(f_{u,0/1,i}\) 开大小为 \(\min(sz_u, \sqrt{n})\) 的 vector，并且合并完立刻销毁。
code
// Problem: D. Mex Tree
// Contest: Codeforces - Codeforces Round 875 (Div. 1)
// URL: https://codeforces.com/contest/1830/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const int B = 450;
const int inf = 0x3f3f3f3f;
int n, sz[maxn], g[maxn];
vector<int> G[maxn], f[maxn][2];
void dfs(int u, int fa) {
vector<int>(2).swap(f[u][0]);
vector<int>(2).swap(f[u][1]);
sz[u] = 1;
for (int v : G[u]) {
if (v == fa) {
continue;
}
dfs(v, u);
for (int x = 0; x <= 1; ++x) {
f[u][x].resize(min(B, sz[u] + sz[v]) + 1);
for (int i = 1; i <= min(B, sz[u] + sz[v]); ++i) {
g[i] = f[u][x][i];
f[u][x][i] = inf;
}
for (int y = 0; y <= 1; ++y) {
for (int i = 1; i <= min(B, sz[u]); ++i) {
for (int j = 1; j <= min(B, sz[v]); ++j) {
if (x ^ y) {
f[u][x][i] = min(f[u][x][i], g[i] + f[v][y][j] + j * (j + 1) / 2 * (y ? 2 : 1));
} else if (i + j <= B) {
f[u][x][i + j] = min(f[u][x][i + j], g[i] + f[v][y][j]);
}
}
}
}
}
sz[u] += sz[v];
vector<int>().swap(f[v][0]);
vector<int>().swap(f[v][1]);
}
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
vector<int>().swap(G[i]);
}
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
dfs(1, -1);
int ans = inf;
for (int i = 1; i <= min(sz[1], B); ++i) {
for (int x = 0; x <= 1; ++x) {
ans = min(ans, f[1][x][i] + i * (i + 1) / 2 * (x ? 2 : 1));
}
}
printf("%lld\n", 1LL * n * (n + 1) - ans);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}