Cod sursa(job #1709484)

Utilizator UNIBUC_Echipa_LachetaBicsi Nitu Velea UNIBUC_Echipa_Lacheta Data 28 mai 2016 12:31:50
Problema Revolta Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 4.09 kb
#include <cassert>
#include <fstream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <bitset>
#include <ctime>
#include <set>
#include <cmath>
#include <iomanip>
#include <map>
#include <stack>
#include <vector>
#include <bitset>

#include <fstream>

using namespace std;

#define FOR(i, a, n) for (int i = a; i <= n; ++i)
#define ROF(i, n, a) for (int i = n; i >= a; i--)
#define FIT(i, v) for (auto &i : v)
#define pb push_back
#define mp make_pair
#define mt make_touple
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
const int mod = 2000003;
ll powmod(ll a, ll b) {ll res=1; a %= mod; assert(b >= 0); for(; b; b >>= 1) {if (b & 1) res = res * a % mod; a = a * a % mod;} return res;}

const int N = 100100;

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

vector<int> v[N];
int sol, diam[N], nrj[N];

void dfb(int x,int p) {
    nrj[x] = 1;
    diam[x] = 1;
    FIT(it,v[x]) {
        if (it == p) {
            continue;
        }
        dfb(it,x);
    }
    int ma1 = 0;
    int ma2 = 0;
    FIT(it,v[x]) {
        if (it == p) {
            continue;
        }
        diam[x] = max(diam[x], diam[it]);
        if (nrj[it] > ma1) {
            ma2 = ma1;
            ma1 = nrj[it];
        } else if (nrj[it] > ma2) {
            ma2 = nrj[it];
        }
        nrj[x] = max(nrj[x], 1 + nrj[it]);
    }
    diam[x] = max(diam[x], ma1 + ma2 + 1);
}

void dfs(int x, int p, int up, int md) {
    int ma1 = 0;
    int ma2 = 0;
    int ma3 = 0;
    int diama1 = 0;
    int diama2 = 0;
    FIT(it,v[x]) {
        if (it == p) {
            continue;
        }
        if (nrj[it] > ma1) {
            ma3 = ma2;
            ma2 = ma1;
            ma1 = nrj[it];
        } else if (nrj[it] > ma2) {
            ma3 = ma2;
            ma2 = nrj[it];
        } else if (nrj[it] > ma3) {
            ma3 = nrj[it];
        }
        
        if (diam[it] > diama1) {
            diama2 = diama1;
            diama1 = diam[it];
        } else if (diam[it] > diama2) {
            diama2 = diam[it];
        }
        
    }
    ma1++; ma2++; ma3++;
    FIT(it,v[x]) {
        if (it == p) {
            continue;
        }
        int diama = md;
        if (diama1 == diam[it]) {
            diama = max(diama, diama2);
        } else {
            diama = max(diama, diama1);
        }
        if (ma1 == nrj[it] + 1) {
            diama = max(diama, up + ma2);
            diama = max(diama, ma2 + ma3 - 1);
        } else if (ma2 == nrj[it] + 1) {
            diama = max(diama, up + ma1);
            diama = max(diama, ma1 + ma3 - 1);
        } else {
            diama = max(diama, up + ma1);
            diama = max(diama, ma1 + ma2 - 1);
        }
        int diamb = diam[it];
        int cs = max(diamb - 1,diama - 1);
        diama /= 2;
        diamb /= 2;
        sol = min(sol, max(1 + diama + diamb, cs));
    }
    FIT(it,v[x]) {
        if (it == p) {
            continue;
        }
        int nup = up + 1;
        int ndm = md;
        if (diama1 == diam[it]) {
            ndm = max(ndm, diama2);
        } else {
            ndm = max(ndm, diama1);
        }
        if (ma1 == nrj[it] + 1) {
            ndm = max(ndm, up + ma2);
            ndm = max(ndm, ma2 + ma3 - 1);
            nup = max(nup, ma2 + 1);
        } else if (ma2 == nrj[it] + 1) {
            ndm = max(ndm, up + ma1);
            ndm = max(ndm, ma1 + ma3 - 1);
            nup = max(nup, ma1 + 1);
        } else {
            ndm = max(ndm, up + ma1);
            ndm = max(ndm, ma1 + ma2 - 1);
            nup = max(nup, ma1 + 1);
        }
        dfs(it,x,nup,ndm);
    }
}
int main() {
    int T;
    fin >> T;
    while (T--) {
        int n;
        fin >> n;
        sol = n + 1;
        FOR(i,1,n - 1) {
            int x, y;
            fin >> x >> y;
            ++x;
            ++y;
            v[x].pb(y);
            v[y].pb(x);
        }
        dfb(1,0);
        dfs(1,0,0,0);
        sol = min(sol, diam[1] - 1);
        FOR(i,1,n) {
            v[i].clear();
            diam[i] = nrj[i] = 0;
        }
        fout << sol << "\n";
    }
}