Tree Coloring (Easy Version)

    1#include <bits/stdc++.h>
    2using namespace std;
    3typedef long long ll;
    4const long long INF = 1e17; //❄️
    5void solve() {
    6    int n; cin >> n;
    7    vector<vector<int>> g(n + 1);
    8    for (int i = 0; i < n - 1; i++) {
    9        int u, v; cin >> u >> v;
    10        g[u].push_back(v);
    11        g[v].push_back(u);
    12    }
    13    vector<int> depth(n + 1, -1), child_cnt(n + 1), cnt_depth(n + 1);
    14    queue<int> q;
    15    depth[1] = 0;
    16    // 1 is root
    17    q.push(1);
    18    int mx_depth = 0;
    19    while (!q.empty()) {
    20        int u = q.front();
    21        q.pop();
    22        int d = depth[u];
    23        cnt_depth[d]++;
    24        mx_depth = max(mx_depth, d);
    25        for (int v : g[u]) {
    26            if (depth[v] == -1) {
    27                depth[v] = d + 1;
    28                // v is child of u
    29                child_cnt[u]++;
    30                q.push(v);
    31            }
    32        }
    33    }
    34    int ans = 0;
    35    for (int i = 0; i <= mx_depth; i++) {
    36        ans = max(ans, cnt_depth[i]);
    37    }
    38    for (int i = 1; i <= n; i++) {
    39        ans = max(ans, 1 + child_cnt[i]);
    40    }
    41    cout << ans << "\n";
    42}
    43int main() {
    44    ios::sync_with_stdio(0); cin.tie(0); 
    45    int t; cin >> t;
    46    while (t--) {
    47        solve();
    48    }
    49    return 0;
    50}