Cod sursa(job #1709591)

Utilizator echipa_BoSSilorUNIBUC Harsan Bicsi Baltatu echipa_BoSSilor Data 28 mai 2016 12:59:57
Problema Revolta Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 2.98 kb
#include <iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

const int N = 100100;

int n, d[N], lant[N], rmin;
vector<int> v[N];
multiset<int> h[N];

void init() {
    int i;

    for(i = 0; i <= n; ++i) {

        v[i].clear();
        h[i].clear();
        d[i] = 0;
        lant[i] = 0;
    }
}

void df(int nod, int p) {

    int l1 = 0, l2 = 0;

    for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it) if(*it != p) {

        df(*it, nod);

        lant[nod] = max(lant[nod], lant[*it] + 1);
        d[nod] = max(d[nod], d[*it]);

        int e = lant[*it] + 1;

        if(e > l1) {
            l2 = l1;
            l1 = e;
        }
        else if(e > l2)
            l2 = e;
    }

    d[nod] = max(d[nod], l1 + l2);

}

void df2(int nod, int p, int dup, int lup) {

    int l1 = lup + 1, l2 = 0;
    h[nod].insert(lup);

    for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it) if(*it != p) {

        int e = lant[*it] + 1;

        h[nod].insert(e);

        if(h[nod].size() > 3)
            h[nod].erase(h[nod].begin());

        ++e;
        if(e > l1) {
            l2 = l1;
            l1 = e;
        }
        else if(e > l2)
            l2 = e;
    }

    int vv = 0;

    for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it) if(*it != p) {
        vv = 1;
        int nlup = l1, ndup = 0;

        if(l1 == lant[*it] + 2)
            nlup = l2;

        ndup = nlup - 1;

        if(h[nod].size() >= 2) {
            bool flag = 0;
            multiset<int>::iterator jt = h[nod].find(lant[*it] + 1);
            if(jt != h[nod].end()) {
                flag = true;
                h[nod].erase(jt);
            }

            if(h[nod].size() >= 2) {

                jt = h[nod].end();
                jt--;
                int sc = *jt;
                --jt;
                sc += *jt;

                ndup = max(ndup, sc);
            }

            if(flag)
                h[nod].insert(lant[*it] + 1);
        }


        int solc = (ndup + 1) / 2 + (d[*it] + 1) / 2 + 1;

        int rc = max(ndup, max(d[*it], solc));

        rmin = min(rmin, rc);


        ndup = max(ndup, nlup);

        df2(*it, nod, ndup, nlup);
    }

    //cout << nod << " " << dup << " " << lup << " " << rmin << "\n";

    if(vv == 0) {

        rmin = min(rmin, max(dup, lup));
    }

}

void sol() {
    int i, j;

    cin >> n;

    init();

    for(i = 1; i < n; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        //a--; b--;

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

    df(0, -1);
rmin = 1000000;
    df2(0, -1, 0, 0);


    cout << min(d[0], rmin) << "\n";
}

int main()
{int i, j;
    freopen("revolta.in", "r", stdin);
    freopen("revolta.out", "w", stdout);

    int t;
    cin >> t;
    while(t--)sol();

    return 0;
}