[题解] Tree III

“第二直径”显然其一端的端点在直径的一端。可以尝试用反证法来进行证明，这里给出一个简单的证明，具体细节留给读者自证：若第二直径的两端都不在直径的端点，那么将第二直径的某一端向直径端点延申，得到的路径长度不降。

因此，我们只需要任意找到一条直径，分别找到他们到每个点的距离，然后寻找到“第三大”的位置（因为同一条直径会计算两次），所以取第三长的路径即为答案。

时间复杂度，空间复杂度

参考代码：

class Solution
{
public:
    int n;
    int d[100010];
    vector<int> v[100010];

    inline void dfs(int x, int fa)
    {
        int sz = v[x].size();
        for (int i = 0; i < sz; ++i)
        {
            if (v[x][i] == fa)
                continue;
            d[v[x][i]] = d[x] + 1;
            dfs(v[x][i], x);
        }
    }
    int tree3(vector<int> &E)
    {
        n = E.size();
        for (int i = 0, x; i < n; ++i)
        {
            v[E[i]].push_back(i + 2), v[i + 2].push_back(E[i]);
        }
        ++n;
        int c = 0, e = 0, f = 0;
        memset(d, 0, sizeof(d));
        dfs(1, 1);
        for (int i = 1; i <= n; ++i)
        {
            if (d[c] < d[i])
                c = i;
        }
        memset(d, 0, sizeof(d));
        dfs(c, c);
        for (int i = 1; i <= n; ++i)
        {
            if (d[e] <= d[i])
                f = e, e = i;
            else if (d[f] <= d[i])
                f = i;
        }
        int ans = d[f];
        memset(d, 0, sizeof(d));
        dfs(e, e);
        c = f = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (d[c] <= d[i])
                f = c, c = i;
            else if (d[f] <= d[i])
                f = i;
        }
        return max(ans, d[f]);
    }
};