Cod sursa(job #1708375)

Utilizator stefanrStefan Ruseti stefanr Data 26 mai 2016 23:04:52
Problema Revolta Scor Ascuns
Compilator cpp Status done
Runda Marime 4.69 kb
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   official.cpp
 * Author: Stefan
 *
 * Created on May 26, 2016, 11:35 AM
 */

#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

#define INF 100000000
#define NMAX 100000
#define UNSET -1

int n;
vector< vector<int> > graph;
vector<bool> visited;
vector<int> dhl;
vector<int> dl;
vector<int> dhr;
vector<int> dr;

void init() {
    graph.assign(n, vector<int>(0));
    dhl.assign(n, UNSET);   
    dl.assign(n, UNSET);
    dhr.assign(n, UNSET);   
    dr.assign(n, UNSET);
}

void dfs(int node, int parent) {
    int maxDepth1 = 0, maxDepth2 = 0;
    int maxDiam1 = 0, maxDiam2 = 0;
    for (int i = 0; i < graph[node].size(); i++) {
        int next = graph[node][i];
        if (next != parent) {
            dfs(next, node);
            if (dhl[next] > maxDepth1) {
                maxDepth2 = maxDepth1;
                maxDepth1 = dhl[next];
            }
            else {
                if (dhl[next] > maxDepth2) {
                    maxDepth2 = dhl[next];
                }
            }
            if (dl[next] > maxDiam1) {
                maxDiam2 = maxDiam1;
                maxDiam1 = dl[next];
            }
            else {
                if (dl[next] > maxDiam2) {
                    maxDiam2 = dl[next];
                }
            }
        }
    }
    dhl[node] = maxDepth1 + 1;
    dl[node] = max(maxDiam1, maxDepth1 + maxDepth2);
}

void updateMax(int *maxValues, int size, int value) {
    for (int i = 0; i < size; i++) {
        if (value > maxValues[i]) {
            for (int j = size - 1; j > i; j--) {
                maxValues[j] = maxValues[j-1];
            }
            maxValues[i] = value;
            break;
        }
    }
}

pair<int, int> topTwo(int *maxValues, int removed) {
    if (maxValues[0] == removed) return pair<int, int>(maxValues[1], maxValues[2]);
    pair<int, int> result;
    result.first = maxValues[0];
    if (maxValues[1] == removed) result.second = maxValues[2];
    else result.second = maxValues[1];
    return result;
}

void dfs2(int node, int parent) {
    int maxDepth[3], maxDiam[3];
    maxDepth[0] = dhr[node];
    maxDiam[0] = dr[node];
    for (int i = 1; i < 3; i++)
        maxDepth[i] = maxDiam[i] = 0;
    for (int i = 0; i < graph[node].size(); i++) {
        int next = graph[node][i];
        if (next != parent) {
            updateMax(maxDepth, 3, dhl[next]);
            updateMax(maxDiam, 3, dl[next]);
        }
    }
    for (int i = 0; i < graph[node].size(); i++) {
        int next = graph[node][i];
        if (next != parent) {
            pair<int, int> top = topTwo(maxDepth, dhl[next]);
            dhr[next] = top.first + 1;
            dr[next] = max(topTwo(maxDiam, dl[next]).first, top.first + top.second);
            dfs2(next, node);
        }
    }
}

vector< pair<int,int> > getEdges() {
    vector< pair<int,int> > result;
    for (int i = 0; i < n - 1; i ++) {
        for (vector<int>::iterator next = graph[i].begin(); next < graph[i].end(); next++) {
            if (i > *next) continue;
            result.push_back(pair<int, int>(i, *next));
        }
    }
    return result;
}

/*
 * 
 */
int main(int argc, char** argv) {

    freopen ("revolta.in","r",stdin);
    freopen ("revolta.out","w",stdout);
    int t;
    scanf("%d", &t);
    while (t-- > 0) {
        scanf("%d", &n);
        init();
        //cout << "init" << endl;
        int a, b;
        for (int i = 0; i < n - 1; i++) {
            scanf("%d %d", &a, &b);
            //cin >> a >> b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        //cout << "read" << endl;
        dfs(0, UNSET);
        dr[0] = 0;
        dhr[0] = 0;
        dfs2(0, UNSET);
        vector< pair<int, int> > edges = getEdges();
        int best = n;
        for (int i = 0; i < edges.size(); i++) {
            int x;
            if (dhl[edges[i].first] > dhl[edges[i].second]) {
                x = edges[i].second;
            }
            else {
                x = edges[i].first;
            }
            int d = dl[x];
            if (dr[x] > d) d = dr[x];
            d = max(d, dr[x] / 2 + dr[x] % 2 + dl[x] / 2 + dl[x] % 2 + 1);
            if (d < best) best = d;
        }
//        for (int i = 0; i < n; i++) {
//            cout << i << ": " << dhr[i] << " " << dr[i] << endl;
//        }
        cout << min(dl[0], best) << endl;
    }
    
    return 0;
}