题目描述

求从某一点到另一点的距离最长（树的直径）

(求树的直径dfs) $O(n)$

先任取一点，求出这一点到其他所有点中，距离最长的，记录这个点；
从这个点出发，找到所有点中，到这个点距离最长的，即为树的直径；
1、vector< edge>h[N] ; int dist[N];
2、void dfs(int u, int father, int distance)
3、思路：找距离点1的最大距离点a，找距离点a的最大距离点b,ab间距离为结果

C++ 代码

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
int n;
struct Edge {
    int id, w;   //边的id，和距离
};
vector<Edge> h[N];  //存放每一个结点的所有邻边
int dist[N];  //距离
void dfs(int u, int father, int distance) //因为是树，所以不存在环，所以这种dfs可以成立
{ 
    dist[u] = distance;   //记录到初始选择的点（结点1）的距离
    for (auto node : h[u])  //遍历遍历这个点的所有邻接点
        if (node.id != father) //这个点不是父节点（可以访问）
            dfs(node.id, u, distance + node.w); //访问子结点
             //注意：a.w+distance赋值给dis[a.id],distance是原来的选中的点到这点的距离
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);  //a到b距离为c
        h[a].push_back({ b, c });
        h[b].push_back({ a, c });
    }
    dfs(1, -1, 0);   //从点1开始，父节点设置为-1，距离为0
    int u = 1;
    for (int i = 1; i <= n; i++) //
        if (dist[i] > dist[u])
            u = i;
    dfs(u, -1, 0);  //u为到结点1最远的点
    for (int i = 1; i <= n; i++)
        if (dist[i] > dist[u])
            u = i;
    int s = dist[u];  //最远距离
    printf("%lld\n", s * 10 + s * (s + 1ll) / 2);
    return 0;
}