Cod sursa(job #1710111)

Utilizator UBB_Craciun_Griza_PuscasUBB ATeamHasNoName UBB_Craciun_Griza_Puscas Data 28 mai 2016 15:43:19
Problema Revolta Scor 0
Compilator cpp Status done
Runda Arhiva ICPC Marime 3.78 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int MAXN = 100100;

int dad[MAXN], bestLant[MAXN], bestLant2[MAXN], diaCur[MAXN], bestDia[MAXN], bestDia2[MAXN], bestLantSus[MAXN];
int fbl[MAXN], fbl2[MAXN], fd[MAXN], fd2[MAXN], n;
vector<int> graph[MAXN];

int bestRez = 3 * MAXN;


void explorare(int nod) {
    for (auto it: graph[nod]) {
        if (it == dad[nod]) continue;

        if (!dad[it]) {
            dad[it] = nod;
            explorare(it);
        }
    }
}

void get_lanturi(int nod) {
    for (auto it: graph[nod]) {
        if (it == dad[nod]) continue;

        get_lanturi(it);

        if (bestLant[it] + 1 > bestLant[nod]) {
            bestLant2[nod] = bestLant[nod];
            fbl2[nod] = fbl[nod];
            bestLant[nod] = bestLant[it] + 1;
            fbl[nod] = it;
        }
        else if (bestLant[it] + 1 > bestLant2[nod]) {
            bestLant2[nod] = bestLant[it] + 1;
            fbl2[nod] = it;
        }
    }
    diaCur[nod] = bestLant[nod] + bestLant2[nod];
}


void get_diametre(int nod) { //vezi frunze
    for (auto it: graph[nod]) {
        if (it == dad[nod]) continue;

        get_diametre(it);

        if (diaCur[it] > diaCur[nod])
            diaCur[nod] = diaCur[it];

        if (diaCur[it] > bestDia[nod]) {
            bestDia2[nod] = bestDia[nod];
            fd2[nod] = fd[nod];
            bestDia[nod] = diaCur[it];
            fd[nod] = it;
        }
        else if (diaCur[it] > bestDia2[nod]) {
            bestDia2[nod] = diaCur[it];
            fd2[nod] = it;
        }
    }
}

void get_lant_sus(int nod) {
    int b1, b2;

    b1 = bestLantSus[dad[nod]] + 1;

    if (fbl[dad[nod]] == nod)
        b2 = bestLant2[dad[nod]] + 1;
    else
        b2 = bestLant[dad[nod]] + 1;
    if (dad[nod] != 0)
        bestLantSus[nod] = max(b1, b2);

    for (auto it: graph[nod]) {
        if (nod != dad[it]) continue;

        get_lant_sus(it);
    }
}


void solve(int nod) {
    for (auto it : graph[nod]) {
        if (it == dad[nod]) continue;

        solve(it);

        int d1 = diaCur[it];

        int d2 = 0;

        if (it == fd[nod])
            d2 = bestDia2[nod];
        else
            d2 = bestDia[nod];

        int l2 = 0;

        if (it == fbl[nod])
            l2 = bestLant2[nod];
        else
            l2 = bestLant[nod];

        int d2bl = 0;

        d2bl = l2  + bestLantSus[nod];

        int d2bd = 0;

        if (nod == fd[dad[nod]])
            d2bd = bestDia2[dad[nod]];
        else
            d2bd = bestDia[dad[nod]];

        int diametru2 = max(d2, max(d2bl, d2bd));


        int rez;

        rez = max(d1, diametru2);
        int newD = d1 / 2 + diametru2 / 2 + 1;
        if (d1 % 2 == 1)
            ++newD;
        if (diametru2 % 2 == 1)
            ++newD;

        rez = max (newD, rez);

        if (rez < bestRez)
            bestRez = rez;
    }
}

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

        fin >> n;
        for (int i = 0; i <= n; ++i) {
            graph[i].clear();
            bestLant[i] = 0;
            bestLant2[i] = 0;
            bestDia[i] = 0;
            bestDia2[i] = 0;
            diaCur[i] = 0;
            bestLantSus[i] = 0;
            dad[i] = 0;
        }

        for (int i = 1; i < n; ++i) {
            int x, y;
            fin >> x >> y;
            ++x; ++y;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }

        explorare(1);
        get_lanturi(1);
        get_diametre(1);
        get_lant_sus(1);

        solve(1);

        fout << bestRez << "\n";
    }

    return 0;


}