Cod sursa(job #1710048)

Utilizator oldscotchUPB Old Scotch oldscotch Data 28 mai 2016 14:53:21
Problema Revolta Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 4.23 kb
#include <cstdio>
#include <vector>
#include <deque>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 100505;
const int INF = 0x3f3f3f3f;
int T, N, maxDown[NMAX], maxDiamDown[NMAX], maxUp[NMAX], maxDiamUp[NMAX];
int par[NMAX];
vector<int> G[NMAX], children[NMAX];
bool mark[NMAX];

void read()
{
    scanf("%d", &N);
    int x, y;
    for (int i = 1; i < N; i++)
    {
        scanf("%d%d", &x, &y);
        x++;
        y++;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void dfs1(int node)
{
    mark[node] = true;
    for (auto& x: G[node])
    {
        if (!mark[x])
        {
            children[node].push_back(x);
            par[x] = node;
            dfs1(x);
            maxDown[node] = max(maxDown[node], maxDown[x] + 1);
        }
    }

    if (!children[node].empty())
    {
        int best1 = 0, best2 = 0;
        for (auto& x: children[node])
        {
            if (maxDown[x] > best1)
            {
                best2 = best1;
                best1 = maxDown[x];
            }
            else if (maxDown[x] > best2)
            {
                best2 = maxDown[x];
            }
        }
        maxDiamDown[node] = best1 + best2 + 1;
    }
}

void dfs2(int node)
{
    priority_queue<pair<int, int>> Q;
    for (auto& x: children[node])
    {
        Q.push({maxDown[x], x});
    }

    bool remCurr;
    for (auto& x: children[node])
    {
        // init for x
        maxUp[x] = maxUp[node] + 1;
        maxDiamUp[x] = maxDiamUp[node];
        remCurr = false;
        if (Q.top().second == x)
        {
            Q.pop();
            remCurr = true;
        }

        if (!Q.empty())
        {
            pair<int, int> best1 = Q.top();
            maxUp[x] = max(maxUp[x], best1.first + 2);
            maxDiamUp[x] = max(maxDiamUp[x], best1.first + 1 + maxUp[node]);
            if (Q.size() > 1)
            {
                Q.pop();
                if (!remCurr && Q.top().second == x)
                {
                    Q.pop();
                    remCurr = true;
                }
                if (!Q.empty())
                {
                    pair<int, int> best2 = Q.top();
                    maxDiamUp[x] = max(maxDiamUp[x], best1.first + best2.first + 2);
                }
                Q.push(best1);
            }
        }
        if (remCurr)
        {
            Q.push({maxDown[x], x});
        }
    }
    // don't forget to take maximum across their diam
    if (children[node].size() > 1)
    {
        while (!Q.empty())
        {
            Q.pop();
        }
        for (auto& x: children[node])
        {
            Q.push({maxDiamDown[x], x});
        }
        for (auto& x: children[node])
        {
            remCurr = false;
            if (Q.top().second == x)
            {

                Q.pop();
                remCurr = true;
            }
            pair<int, int> best1 = Q.top();
            maxDiamUp[x] = max(maxDiamUp[x], best1.first);
            if (remCurr)
            {
                Q.push({maxDown[x], x});
            }
        }
    }

    for (auto& x: children[node])
    {
        dfs2(x);
    }
}

inline int upperBound2(int x)
{
    return x % 2 ? x / 2 + 1 : x / 2;
}

void solve()
{
    int result = INF;
    for (int i = 1; i <= N; i++)
    {
        int cand = max(maxDiamDown[i], maxUp[i]);
        cand = max(cand, 1 + upperBound2(maxDiamDown[i]) + upperBound2(maxDiamUp[i]));
        result = min(result, cand);
    }
    printf("%d\n", result);
}

void clear()
{
    for (int i = 1; i <= N; i++)
    {
        G[i].clear();
        children[i].clear();
    }
    memset(mark, false, sizeof(mark));
    memset(par, 0, sizeof(par));
    memset(maxDown, 0, sizeof(maxDown));
    memset(maxDiamDown, 0, sizeof(maxDiamDown));
    memset(maxUp, 0, sizeof(maxUp));
    memset(maxDiamUp, 0, sizeof(maxDiamUp));
}

int main()
{
    freopen("revolta.in", "r", stdin);
    freopen("revolta.out", "w", stdout);
    scanf("%d", &T);
    while (T--)
    {
        read();
        dfs1(1);
        dfs2(1);
        solve();
        clear();
    }

    return 0;

}