Cod sursa(job #2456058)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 13 septembrie 2019 13:48:24
Problema Revolta Scor 0
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 4.14 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream f("revolta.in");
ofstream g("revolta.out");
int N, cnt, d, Deep[100005], Arb[2][400005];
queue <int> Q;
vector <int> G[100005];
int DistL[100005], DistR[100005];
int Used[100005], Diam[100005], D[100005], Dist[100005], Left[100005], Right[100005],TT[100005];
void Read(){
    f >> N;
    for(int i = 1; i < N; i++){
        int x, y;

        f >> x >> y;
        ++x;++y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void BFS(int start){
    for(int i = 1; i <= N; i++)
        Used[i] = 0, Dist[i] = -1;
    Q.push(start);
    Used[start] = 1;
    while(!Q.empty()){
        int node = Q.front();
        Q.pop();
        for(int i = 0; i < G[node].size(); i++){
            int neighb = G[node][i];
            if(!Used[neighb]){
                Used[neighb] = 1;
                TT[neighb] = node;
                Dist[neighb] = Dist[node] + 1;
                Q.push(neighb);
            }
        }
    }
}

void findDiameter(){
    BFS(1);
    int Max = -1, PMax = 0;
    for(int i = 1; i <= N; i++){
        if(Dist[i] > Max){
            Max = Dist[i];
            PMax = i;
        }
    }
    BFS(PMax);
    int PMax2 = 0;
    Max = -1;
    for(int i = 1; i <= N; i++){
        if(Dist[i] > Max){
            Max = Dist[i];
            PMax2 = i;
        }
    }
    int x = PMax, y = PMax2;
    int node = y;
    d = Dist[y] + 1;
    while(node != x){
        Diam[node] = 1;
        D[++cnt] = node;
        node = TT[node];
    }
    Diam[x] = 1;
    D[++cnt] = x;
}

void DFS(int node, int father, int level, int root){
    Deep[root] = max(Deep[root], level);
    for(int i = 0; i < G[node].size(); i++){
        int neighb = G[node][i];
        if(neighb == father)
            continue;
        DFS(neighb, node, level + 1, root);
    }
}
void buildTree(int K, int L, int R){
    if(L == R){
        Arb[0][K] = Deep[D[L]] + L;
        Arb[1][K] = Deep[D[L]] - L;
        return;
    }
    buildTree(K * 2, L, (L + R) / 2);
    buildTree(K * 2 + 1, ( L+ R) / 2 + 1, R);
    Arb[0][K] = max(Arb[0][K * 2], Arb[0][K * 2 + 1]);
    Arb[1][K] = max(Arb[1][K * 2], Arb[1][K * 2 + 1]);
}

int query(int ind, int K , int L, int R, int x, int y){
    if(L > R || L > y || R < x)
        return -1;
    if(L >= x && R <= y)
        return Arb[ind][K];
    return max(query(ind, K * 2, L, (L + R) / 2, x, y), query(ind, K * 2 + 1, (L + R) / 2 + 1, R, x, y));
}
int getVal(int pos, int right){
    return max(query(1, 1, 1, cnt, 1, pos - 1) + pos, query(0, 1, 1, cnt, pos, right) - pos);
}
void Solve(){
    for(int i = 1; i <= cnt; i++){
        int root = D[i];
        for(int j = 0; j < G[root].size(); j++){
            int neighb = G[root][j];
            if(Diam[neighb])
                continue;
            DFS(neighb, root, 1, root);
        }
    }
    buildTree(1, 1, cnt);
    Left[1] = 0;
    DistL[1] = 0;
    int Max = 1, leftVal = 0;
    for(int i = 2; i <= cnt; i++){
        int node = D[i];
        DistL[i] = max(DistL[i - 1], query(1, 1, 1, cnt, 1, i - 1) + i + Deep[D[i]]);
        while(Max < i && getVal(Max, i) >= getVal(Max + 1, i)){
            ++Max;
        }
        Left[i] = getVal(Max, i);
    }
    reverse(D + 1, D + cnt + 1);
    buildTree(1, 1, cnt);
    Right[cnt] = DistR[cnt] = 0;
    Max = 1;
    for(int i = 2; i <= cnt; i++){
        while(Max < i && getVal(Max, i) >= getVal(Max + 1, i)){
            ++Max;
        }
        DistR[cnt - i + 1] = max(DistR[i + 1], query(1, 1, 1, cnt, 1, i - 1) + i + Deep[D[i]]);
        Right[cnt - i + 1] = getVal(Max, i);
    }
    int ans = d;
    for(int i = 1; i < cnt; i++){
        ans = min(ans, max(max(Left[i] + Right[i + 1] + 1, DistL[i]), DistR[i + 1]));
    }
    g << ans << '\n';
}
int main()
{
    int T;
    f >> T;
    while(T--){
        Read();
        findDiameter();
        Solve();
        for(int i = 1; i <= N; i++){
            G[i].clear();
            Diam[i] = 0;
            Deep[i] = 0;
        }
        cnt = 0;
    }

    return 0;
}