zoj 3820(2014牡丹江現場試合B題)

タイトルリンク:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5374
構想:テーマの意味は木の上の2点を求めて、木の上の残りの点からその中の1つの点までの最長距離を最小にします.この問題は木の直径と関係があると考えることができます.まず木の直径を求めて、それから木の中点とその中点に隣接して、直径の上の1つの点を取り出して、このようにこの木を2つの子木に分けて、それからそれぞれこの2つの木の直径を求めて、最後に選択する2つの点はそれぞれこの2つの木の直径の上の中点です.
最初はdfsで書いたのですが、結局爆桟してbfsに変更すると過ぎてしまいました.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int MAX_N = (200000 + 20000);
struct Edge {
    int v, w, next;
} edge[MAX_N << 1];

int N, NE, head[MAX_N];
void Init()
{
    NE = 0;
    memset(head, -1, sizeof(head));
}

void Insert(int u, int v, int w)
{
    edge[NE].v = v;
    edge[NE].w = w;
    edge[NE].next = head[u];
    head[u] = NE++;
}

int dep[MAX_N], path[MAX_N], st, ed, s_mid, e_mid;
int ans_minDist, ans_point1, ans_point2;
bool vis[MAX_N];

bool check(int u, int v)
{
    if (u == s_mid && v == e_mid) return true;
    if (u == e_mid && v == s_mid) return true;
    return false;
}

void bfs(int u, int fa, int deep)
{
    dep[u] = deep;
    path[u] = fa;
    vis[u] = true;
    queue<int > que;
    que.push(u);

    while (!que.empty()) {
        int u = que.front();
        que.pop();

        for (int i = head[u]; ~i; i = edge[i].next) {
             int v = edge[i].v, w = edge[i].w;
             if (v == fa || check(u, v) || vis[v]) continue;
             dep[v] = dep[u] + w;
             path[v] = u;
             vis[v] = true;
             que.push(v);
        }
    }
}

void gao()
{
    s_mid = e_mid = -1;
    memset(vis, false, sizeof(vis));
    bfs(1, -1, 0);

    int max_deep = -1;
    for (int i = 1; i <= N; ++i) {
        if (dep[i] > max_deep) max_deep = dep[i], st = i;
    }

    memset(vis, false, sizeof(vis));
    bfs(st, -1, 0);

    max_deep = -1;
    for (int i = 1; i <= N; ++i) {
        if (dep[i] > max_deep) max_deep = dep[i], ed = i;
    }

    int tmp = ed, cnt = 0;
    while (tmp != -1) {
        tmp = path[tmp];
        ++cnt;
        if (cnt == max_deep / 2) s_mid = tmp;
        else if (cnt == max_deep / 2 + 1) e_mid = tmp;
    }
}


void solve()
{
    //get point1
    memset(vis, false, sizeof(vis));
    bfs(s_mid, e_mid, 0);

    int max_deep = -1;
    for (int i = 1; i <= N; ++i) {
        if (vis[i] && dep[i] > max_deep) max_deep = dep[i], st = i;
    }

    memset(vis, false, sizeof(vis));
    bfs(st, -1, 0);

    max_deep = -1;
    for (int i = 1; i <= N; ++i) {
        if (vis[i] && dep[i] > max_deep) max_deep = dep[i], ed = i;
    }

    int tmp = ed, cnt = 0;
    ans_point1 = ed;
    while (tmp != -1) {
        tmp = path[tmp];
        ++cnt;
        if (cnt ==  max_deep / 2) ans_point1 = tmp;
    }


    memset(vis, false, sizeof(vis));
    bfs(ans_point1, -1, 0);

    max_deep = -1;
    for (int i = 1; i <= N; ++i) {
        if (vis[i] && dep[i] > max_deep) max_deep = dep[i];
    }

    ans_minDist = max_deep;



    //get point2
    memset(vis, false, sizeof(vis));
    bfs(e_mid, s_mid, 0);

    max_deep = -1;
    for (int i = 1; i <= N; ++i) {
        if (vis[i] && dep[i] > max_deep) max_deep = dep[i], st = i;
    }

    memset(vis, false, sizeof(vis));
    bfs(st, -1, 0);

    max_deep = -1;
    for (int i = 1; i <= N; ++i) {
        if (vis[i] && dep[i] > max_deep) max_deep = dep[i], ed = i;
    }

    tmp = ed, ans_point2 = ed, cnt = 0;
    while (tmp != -1) {
        tmp = path[tmp];
        ++cnt;
        if (cnt == max_deep / 2) ans_point2 = tmp;
    }


    memset(vis, false, sizeof(vis));
    bfs(ans_point2, -1, 0);

    max_deep = -1;
    for (int i = 1; i <= N; ++i) {
        if (vis[i] && dep[i] > max_deep) max_deep = dep[i];
    }

    ans_minDist = max(ans_minDist, max_deep);


}

int main()
{
    int Cas;
    scanf("%d", &Cas);
    while (Cas--) {
        scanf("%d", &N);


        Init();
        for (int i = 1; i < N; ++i) {
            int u, v;
            scanf("%d %d", &u, &v);
            Insert(u, v, 1);
            Insert(v, u, 1);
        }

        if (N == 2) {
            puts("0 1 2");
            continue;
        }

        gao();
        solve();

        printf("%d %d %d
", ans_minDist, ans_point1, ans_point2);
    }
}