Cod sursa(job #1710323)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 28 mai 2016 19:58:56
Problema Revolta Scor 0
Compilator cpp Status done
Runda Arhiva ICPC Marime 3.1 kb
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

const int NMAX = 100005;

int n, ans;
int up[NMAX];
int wave[NMAX];
int max_diameter[NMAX];
pii down[3][NMAX];
vector<int> v[NMAX];

void reset() {
    ans = 0;
    for (int i = 1; i <= n; i++) {
        v[i].clear();
        up[i] = 0;
        wave[i] = 0;
        max_diameter[i] = 0;
        for (int j = 0; j < 3; j++)
            down[j][i] = {0, 0};
    }
}

void dfs_down(int x, int f) {
    for (auto it : v[x]) {
        if (it != f) {
            dfs_down(it, x);

            int new_chain = 1 + down[0][it].fi;
            for (int j = 0; j < 3; j++) {
                if (new_chain > down[j][x].fi) {
                    for (int k = 2; k > j; k--) {
                        down[k][x] = down[k - 1][x];
                    }
                    down[j][x] = {new_chain, it};
                    break;
                }
            }

            max_diameter[x] = max(max_diameter[x], max_diameter[it]);
        }
    }

    max_diameter[x] = max(max_diameter[x], down[0][x].fi + down[1][x].fi);
    ans = max(ans, max_diameter[x]);
}

void dfs_up(int x, int f) {
    for (auto it : v[x]) {
        if (it != f) {
            if (f) {
                int best_down;
                if (down[0][f].se == x) {
                    best_down = down[1][f].fi;
                } else {
                    best_down = down[0][f].fi;
                }
                up[x] = max(1 + up[f], 1 + best_down);
            } else {
                up[x] = 0;
            }

            int best_wave;
            if (down[0][x].se == it) {
                best_wave = down[1][x].fi + down[2][x].fi;
            } else if (down[1][x].se == it) {
                best_wave = down[0][x].fi + down[2][x].fi;
            } else {
                best_wave = down[0][x].fi + down[1][x].fi;
            }
            wave[x] = max(wave[f], best_wave);

            int best_down;
            if (down[0][x].se == it) {
                best_down = down[1][x].fi;
            } else {
                best_down = down[0][x].fi;
            }

            int diameter_up = max(wave[x], up[x] + best_down);
            int diameter_down = max_diameter[it];

            int diameter_cut = max(diameter_up, diameter_down);
            diameter_cut = max(diameter_cut, (diameter_up + 1) / 2 + (diameter_down + 1) / 2 + 1);
            ans = min(ans, diameter_cut);

            dfs_up(it, x);
        }
    }
}

int main() {
    cin.sync_with_stdio(false);

    freopen("revolta.in", "r", stdin);
    freopen("revolta.out", "w", stdout);

    int t;
    cin >> t;
    for (; t; t--) {
        cin >> n;
        reset();

        for (int i = 1; i < n; i++) {
            int x, y;
            cin >> x >> y;
            x++;
            y++;
            v[x].pb(y);
            v[y].pb(x);
        }

        dfs_down(1, 0);
        dfs_up(1, 0);

        cout << ans << '\n';
    }

    return 0;
}