很显然移动时间 $f$ 是固定的 $n$ ，因为 $1$ 秒可以进入一个节点。我们要考虑怎么减少等待时间。因为模拟几个样例可以发现，如何选择最后的结果是固定的，那么我们可以从根节点往下遍历深度，每次等待的时间都是剩下的节点数减去当前节点的深度，所以等待时间就是 $\frac{n\times (n-1)}{2} - \sum\limits_{i=1}^n dep_i$。

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

void solve() {
	int n;
	std::cin >> n;
	std::vector<std::vector<int>> e(n + 1);
	for (int i = 1; i < n; i++) {
		int u, v;
		std::cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	i64 ans = 1LL * n * (n - 1) / 2;
	auto dfs = [&](auto &self, int u, int fa, int depth) -> void {
		ans -= depth;
		for (auto v : e[u]) {
			if (v == fa) {
				continue;
			}
			self(self, v, u, depth + 1);
		}
	};

	dfs(dfs, 1, 0, 0);

	std::cout << n + ans << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t; 
	std::cin >> t;
	while (t --) {
		solve();
	}

	return 0;
}