Cod sursa(job #1541248)

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

using namespace std;

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()
{
    ifstream 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;
}