ReduceDiameter.md

Ответ = общее количество листьев минус максимальное количество листьев, которые можно подключить к одной вершине за одну операцию.

void solve(){
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vvl graph(n); // храним граф
        vl deg(n);    // храним кол-во связанных в-н для к-ой в-ны

        forn(i,0,n-1){
            ll u,v;
            cin>>v>>u;
            v--;u--;
            graph[v].pb(u);
            graph[u].pb(v);
            deg[v]++;deg[u]++; //подсчет связ-ых в-н
        }
        if (n<=3){
            cout<<0<<en; // если в0н меньше 3, то дерево уже с мин диаметром
            continue;
        }

        ll cnt=0, mx=0; // храним кол-во листов и макс кол-во листов у в-ны
        for (auto g: graph){
            ll cnt_v=0; // кол-во листов у к-ой отдельной в-ны
            for (auto c:g){ // проходимся по связ-ым в-нам и считаем листы
                if (deg[c]==1)
                    cnt_v++;
            }
            mx = max(mx,cnt_v);
            cnt+=cnt_v; // собираем общее кол-во листов
        }

        cout<<cnt-mx<<en; // ответ = общее кол-во листов - макс кол-во листов от одной в-ны
    }
}