Cod sursa(job #2622070)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 31 mai 2020 14:00:53
Problema Zvon Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <cstdio>
#include <cctype>
 
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;
 
    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }
 
public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }
    
    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
    
    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

InParser 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].clear();
            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;
}