Cod sursa(job #2622038)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 31 mai 2020 13:12:36
Problema Zvon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

vector <int> v[100001];
int c[100001];

inline int max(int a, int b)
{
    if (a > b)
        return a;
    return b;
}

void dfs(int r)
{
    int i;
    c[r] = 1;
    vector <int> a;
    for (i = 0; i<v[r].size(); i++)
        if (c[v[r][i]] == 0)
        {
            dfs(v[r][i]);
            a.push_back(c[v[r][i]]);
        }
    sort(a.begin(), a.end());
    for (i = 0; i<a.size(); i++)
        c[r] = max(c[r], a[i] + a.size()-i-1);
    if (a.size() > 0)
        c[r]++;
}

int main()
{
    int t, it, i, n, x, y;
    fin >> t;
    for (it = 1; it<=t; it++)
    {
        fin >> n;
        for (i = 1; i<=n; i++)
        {
            v[i] = vector <int>();
            c[i] = 0;
        }
        for (i = 1; i<n; i++)
        {
            fin >> x >> y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        dfs(1);
        fout << c[1]-1 << '\n';
    }
    return 0;
}