九度 1536：树的最小高度

题目描述：

给定一棵无向树， 我们选择不同的节点作为根节点时，可以得到不同的高度（即树根节点到叶子节点距离的最大值）， 现在求这棵树可能的最低高度。

思路

1. 刚开始题目都没看懂. 树的高度, 指的是根节点到叶节点的最大值, 我们要做的是找到最大值中的最小值

2. 查了下资料, 发现这道题是裸求树的直径

3. 树的直径可以用动规求解, 但基本的求法是用两次 BFS(DFS)

4. BFS 的求解过程为, (1) 从任意节点 u 出发, 找到其能够达到的最远的节点 v (2) 再从 v 出发, 找到其能够达到的最远的节点 o (3) v,o 之间的距离就是树的直径 (4) 直径的一半就是所要求的高度

证明 4 的正确性

1. 假设 u 节点就在直径上. 假设 v 不在直径上, 那么必然有一点 v2 在直径上, 且 dis(u, v2) > dis(u,v), 这与 v 是 u 出发到达最远的点矛盾, 所以 v 在直径上(并且肯定在直径的一端)

2. 假设 u 不在直径上, 那么 v 一定在直径上, 否则必然存在一个节点 v2 在直径上, 且 dis(u, v2) > dis(u,v)....

3. 总之, v 一定在直径的一端, o 在另一端

4. 关键点那题与这道类似

代码

用 dfs 做的, bfs 记录深度不太方便 

#include <iostream>
#include <stdio.h>
#include <vector>
#include <memory.h>
#include <deque>
using namespace std;

vector<int> tree[1000010];
bool visited[1000010];

int depthIndex, maxDepth;
void dfs(int n, int depth) {
    if(depth > maxDepth) {
        depthIndex = n;
        maxDepth = depth;
    }

    for(int i = 0; i < tree[n].size(); i ++) {
        int j = tree[n][i];
        if(visited[j]) continue;
        visited[j] = true;
        dfs(j, depth+1);
    }
}
int main() {
    //freopen("testcase.txt", "r", stdin);
    int n;
    while(scanf("%d", &n) != EOF) {
        if(n == 1) {
            cout << 0 << endl;
            continue;
        }else if(n == 2) {
            cout << 1 << endl;
            int a,b;
            scanf("%d%d", &a, &b);
            continue;
        }

        int a, b;
        for(int i = 0; i < n; i++)
            tree[i].clear();

        for(int i = 0; i < n-1; i ++) {
            scanf("%d%d", &a, &b);
            tree[a].push_back(b);
            tree[b].push_back(a);
        }

        maxDepth = 0;
        depthIndex = 0;
        memset(visited, 0, n+10);
        visited[0] = 1;
        dfs(0,0);

        memset(visited, 0, n+10);
        maxDepth = 0;
        visited[depthIndex] = 0;
        dfs(depthIndex, 0);

        int resVal = maxDepth-((maxDepth)>>1);
        printf("%d
", resVal);
    }
    return 0;
}