Cod sursa(job #2705788)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 13 februarie 2021 12:26:27
Problema Zvon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>

#define NMAX 100005
using namespace std;

ifstream fin("zvon.in");
ofstream fout("zvon.out");

vector<int> G[NMAX];
int dp[NMAX], lg[NMAX];

void COUNTA(int nod, int tata)
{
    for(auto it: G[nod])
        if(it != tata)
        {
            COUNTA(it, nod);
            lg[nod] += lg[it];
        }
    if(G[nod].size() == 1)
        lg[nod] = 1;
}

void DFS(int nod, int tata)
{
    vector<pair<int, int > > vec;
    for(auto it: G[nod])
        if(it != tata)
            vec.push_back({lg[it], it});
    sort(vec.begin(), vec.end(), greater<pair<int, int> >());
    int cnt = 1;
    for(auto it: vec)
    {
        int nd = it.second;
        DFS(nd, nod);
        dp[nod] = max(dp[nod], dp[nd] + cnt);
        ++cnt;
    }
}

int main()
{
    int t;
    fin >> t;

    while(t--)
    {
        int n;
        fin >> n;

        for(int i = 1; i < n; ++i)
        {
            int x, y;
            fin >> x >> y;

            G[x].emplace_back(y);
            G[y].emplace_back(x);
        }

        COUNTA(1, 0);
        DFS(1, 0);

        fout << dp[1] << '\n';

        for(int i = 1; i <= n; ++i)
            dp[i] = 0, G[i].clear(), lg[i] = 0;
    }
    return 0;
}