算法思路

这道题卡的是找到任意两个点之间的最大距离和次大距离，之前已经做过类似的题但是用的是暴力求解O(n^2)但是本题n = 1e5 会超时因此需要一个logn做法。其他步骤不变。
做法：用倍增求LCA的的思想在求每个点向上走2^k步的同时维护这一段的最大距离和次大距离，
d1[i][j]， d2[i][j] 分别表示i向上走2^k步经过的路径的最大距离和次大距离
通过递推可以求得

                    for(int k = 1; k <= 16; k ++)
                    {
                        int anc = f[j][k - 1];
                        f[j][k] = f[anc][k - 1];
                        // 最大值和次大值一定就是下面四个值的最大值和次大值
                        int dis[] = {d1[j][k - 1], d2[j][k - 1], d1[anc][k - 1], d2[anc][k - 1]};
                        int maxv = -INF, minv = -INF;
                        for(int u = 0; u < 4; u ++)
                        {
                            if(dis[u] > maxv)minv = maxv, maxv = dis[u];
                            else if(dis[u] != maxv && dis[u] > minv)minv = dis[u];
                        }
                        d1[j][k] = maxv;
                        d2[j][k] = minv;
                    }