ZOJ 3820:Building Fire Stations(树的直径 Grade C)

题意：

n个点的树，边长全为1，求找出两个点，使得树上离这两个点距离最远的那个点，到这两个点（中某个点就行）的距离最小。

思路：

求树直径，找中点，删除中间那条边（如果直径上点数为奇数，则删任何一侧都可），分成两个子树，再求中心，即为答案。

代码：

//14:12
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 200100

struct Graph{
    struct Edge{
        int to;
        int next;
    }e[N*3];
    int head[N];
    int p;
    void clear() {
        p = 0;
        memset(head, -1, sizeof(head));
    }
    void addedge(int u, int v) {
        e[p].to = v;
        e[p].next = head[u];
        head[u] = p++;
    }
}g;

int n;
int dis[N];
int que[N*10];
bool vis[N];
int fa[N];

void generateDis(const Graph &g, int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(fa, -1, sizeof(fa));
    dis[s] = 0;
    int hd = 0;
    int tl = 0;
    que[tl++] = s;
    vis[s] = 1;
    while (hd < tl) {
        int now = que[hd++];
        vis[now] = 0;
        for (int i = g.head[now]; i != -1; i = g.e[i].next) {
            int to = g.e[i].to;
            if (dis[to] > dis[now]+1) {
                dis[to] = dis[now]+1;
                if (!vis[to]) {
                    vis[to] = 1;
                    fa[to] = now;
                    que[tl++] = to;
                }
            }
        }
    }
}

pair<int, int> getTreeMidPoint(const Graph &g, int s, int &OUT_dis) {
    generateDis(g, s);
    for (int i = 1; i <= n; i++) {
        if (dis[i] == 0x3f3f3f3f) dis[i] = -1;
    }
    int u = max_element(&dis[1], &dis[1]+n) - dis;
    
    generateDis(g, u);
    for (int i = 1; i <= n; i++) {
        if (dis[i] == 0x3f3f3f3f) dis[i] = -1;
    }
    int v = max_element(&dis[1], &dis[1]+n) - dis;

    //printf("u = %d, v = %d, dis[v] = %d
", u, v, dis[v]);

    int now = v;
    while (dis[now] > (dis[v]+1)/2) {
        now = fa[now];
    }

    OUT_dis = dis[v]/2 + dis[v]%2;
    return {fa[now], now};
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);

        g.clear();
        for (int i = 0; i < n-1; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            g.addedge(a,b);
            g.addedge(b,a);
        }

        int tmpdis[2];
        pair<int ,int> point = getTreeMidPoint(g, 1, tmpdis[0]);
        
        //printf("all tree get (%d %d, dis=%d)
", point.first, point.second, tmpdis[0]);

        for (int i = g.head[point.first]; i != -1; i=g.e[i].next) {
            if (g.e[i].to == point.second) g.e[i].to = point.first;
        }

        for (int i = g.head[point.second]; i != -1; i=g.e[i].next) {
            if (g.e[i].to == point.first) g.e[i].to = point.second;
        }

        pair<int ,int> pa = getTreeMidPoint(g, point.first, tmpdis[0]);
        pair<int ,int> pb = getTreeMidPoint(g, point.second, tmpdis[1]);

        printf("%d %d %d
", max(tmpdis[0], tmpdis[1]), pa.second, pb.second);
    }
    return 0;
}