Участник:Andriygav/GCPC11J

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/GCPC11J/

#include <iostream>
using namespace std;
int E, to[524288], last[262144], next_[524288], n, t;
int seen[262144], yes, d[262144], q[262144], *head, *tail;
 
int bfs( int src, int *router){
    int x, y, D = -1;
    for(seen[src]=++yes, head = tail = q, d[*tail++ = src] = 0; head < tail;){
        for(int i = last[x = *head++]; i >= 0; i = next_[i]){
            if(seen[y = to[i]] != yes) {
                d[y] = d[x]+1, seen[*tail++ = y] = yes;
                if( d[y] > D){
                    D = d[*router = y];
                }
            }
        }
    }
    return D;
}
 
int main() {
    cin >> t;
    while(t--){
        cin >> n;
        E = 0;
        for(int i = 0; i < n; i++){
            last[i] = -1;
        }
        for(int k = 0; k < n - 1; k++){
            int i, j;
            cin >> i >> j;
            to[E] = j;
            next_[E] = last[i];
            last[i] = E;
            to[E + 1] = i;
            next_[E + 1] = last[j];
            last[j] = E + 1;
            E += 2;
        }
        int router, temp = 0;
        bfs(0, &router);
        int answ = bfs(router, &temp);
 
        if(answ % 2 != 0){
            cout << (answ+1)/2 << endl;
        }else{
            cout << answ/2 << endl;
        }
    }
    return 0;
}