Cod sursa(job #1541250)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 3 decembrie 2015 21:22:09
Problema Zvon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

class InputReader {
    public:
        InputReader() {}
        InputReader(const char *file_name) {
            input_file = fopen(file_name, "r");
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
        inline InputReader &operator >>(int &n) {
            while(buffer[cursor] < '0' || buffer[cursor] > '9') {
                advance();
            }
            n = 0;
            while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            return *this;
        }
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        int cursor;
        char buffer[SIZE];
        inline void advance() {
            ++ cursor;
            if(cursor == SIZE) {
                cursor = 0;
                fread(buffer, SIZE, 1, input_file);
            }
        }
};

const int NMAX = 100005;

vector <int> graph[NMAX];

int dp[NMAX];

bool cmp (int a, int b) {
    return dp[a] > dp[b];
}

void dfs (int node, int father) {
    int pos_father = -1;
    for (int i = 0; i < graph[node].size(); ++ i)
        if (graph[node][i] != father)
            dfs(graph[node][i], node);
        else
            pos_father = i;

    if (pos_father != -1) {
        swap(graph[node][pos_father], graph[node][graph[node].size() - 1]);
        graph[node].pop_back();
    }

    dp[node] = 0;

    sort(graph[node].begin(), graph[node].end(), cmp);
    for (int i = 0; i < graph[node].size(); ++ i)
        if (dp[graph[node][i]] + i + 1 > dp[node])
            dp[node] = dp[graph[node][i]] + i + 1;
}

int main()
{
    InputReader cin("zvon.in");
    ofstream cout("zvon.out");

    int t = 0;
    cin >> t;

    while (t --) {
        int n = 0;
        cin >> n;

        for (int i = 1; i <= n; ++ i)
            graph[i].clear();

        int a, b;
        for (int i = 1; i < n; ++ i) {
            cin >> a >> b;

            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        if (n == 1)
            cout << "0\n";
        else {
            dfs(1, 0);
            cout << dp[1] << '\n';
        }
    }

    //cin.close();
    cout.close();
    return 0;
}