40pts

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;

vector<int> e[N];  // 邻接表存储树
struct Node {
    int a, b;  // 存储每条边的两个端点
} edges[N];
LL ans;  // 最终答案，可能很大，用long long
int sz[N], tot;  // sz[u]表示以当前根为基准时，u的子树大小；tot表示当前连通分量的大小

/*
 * dfs1函数：计算以fa为父节点时，以u为根的子树大小
 * 参数：u - 当前节点，fa - 父节点
 * 功能：遍历整棵树，计算每个节点的子树大小
 */
void dfs1(int u, int fa) {
    sz[u] = 1;  // 初始化：当前节点自身大小为1
    for (int j : e[u]) {
        if (j == fa) continue;  // 跳过父节点，避免回走
        dfs1(j, u);  // 递归处理子节点
        sz[u] += sz[j];  // 累加子树的节点数
    }
}

/*
 * dfs2函数：查找当前连通分量的所有重心并累加到答案中
 * 参数：u - 当前节点，fa - 父节点
 * 功能：遍历整棵树，判断每个节点是否是重心
 * 重心定义：删除该节点后，所有连通分量大小都不超过 tot/2
 */
void dfs2(int u, int fa) {
    bool f = true;  // 标记当前节点是否满足重心条件
    for (int j : e[u]) {
        if (j == fa) continue;
        dfs2(j, u);  // 先递归处理子节点，因为需要遍历所有节点
        if (sz[j] > tot / 2) f = false;  // 检查子节点方向的子树大小
    }
    // 检查父节点方向的子树大小（即除了u的子树外的所有节点）
    if (tot - sz[u] > tot / 2) f = false;
    if (f) ans += u;  // 如果是重心，将节点编号加入答案
}

int main() {
    int _;
    cin >> _;  // 读取测试数据组数
    while (_ --) {
        int n;
        cin >> n;  // 读取当前树的节点数
        
        // 清空邻接表
        for (int i = 1; i <= n; i ++) e[i].clear();
        
        // 读取n-1条边
        for (int i = 1; i < n; i ++) {
            int a, b;
            cin >> a >> b;
            e[a].push_back(b);
            e[b].push_back(a);
            edges[i] = {a, b};  // 存储边
        }
        
        ans = 0;  // 初始化答案
        
        /*
         * 核心逻辑：对每条边分别处理
         * 删除边(a,b)后，树分裂成两个连通分量：
         * 1. a所在的连通分量（从a开始DFS，不经过b）
         * 2. b所在的连通分量（从b开始DFS，不经过a）
         */
        for (int i = 1; i < n; i ++) {
            int a = edges[i].a, b = edges[i].b;
            
            // 处理a所在的连通分量
            dfs1(a, b);  // 以b为父节点，从a开始DFS，计算子树大小
            tot = sz[a];  // 该连通分量的大小就是sz[a]
            dfs2(a, b);  // 在该连通分量中查找所有重心并累加
            
            // 处理b所在的连通分量
            dfs1(b, a);  // 以a为父节点，从b开始DFS，计算子树大小
            tot = sz[b];  // 该连通分量的大小就是sz[b]
            dfs2(b, a);  // 在该连通分量中查找所有重心并累加
        }
        
        cout << ans << "\n";  // 输出答案
    }
    return 0;
}