AcWing 1072. 树的最长路径

题目传送门

#include 

using namespace std;

//树的最长路径，也称为树的直径,直径不唯一

//找树的直径[经典作法]
//1、任取一点作为起点，找到距离该点最远的一个点u，dfs,bfs都行，建议用bfs, 因为dfs可能会爆栈
//2、再找到距离u最远的一个点v.
//3、那么u和v这间的路径就是一条直径。
//证明：离散数学（略）
const int N = 10010;//点数上限
const int M = N * 2;//边数上限
int n;
int h[N], e[M], w[M], ne[M], idx;//邻接表保存树
int ans;
int d1[N], d2[N];

//邻接表加边模板
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

//u:从哪个节点出发
//father:上一个节点是谁，防止走加头路
void dfs(int u, int father) {
    //d1:u结点下第一长路径
    //d2:u结点下第二长路径
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == father)continue;//不走回头路
        //从j出发可以到达的最长距离+(u->j)的路径权重
        dfs(j, u);
        //如果子节点j的最大长度+1,可以更新u节点的最大长度
        if (d1[j] + w[i] >= d1[u]) d2[u] = d1[u], d1[u] = d1[j] + w[i];
        else if (d1[j] + w[i] > d2[u]) d2[u] = d1[j] + w[i];//更新次长节点
    }
    //更新结果
    ans = max(ans, d1[u] + d2[u]);
}


int main() {
    cin >> n;
    //初始化邻接表
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        //无向图，双向建边
        add(a, b, c), add(b, a, c);
    }
    //由于我们可以任取一个点作为根节点，这里取一号点为根节点
    dfs(1, -1);//第二个参数是为了防止走回头路，因为1号节点不是从某个节点过来的，所以传入了-1
    printf("%d", ans);
    return 0;
}