博客

题目传送门：

树的最长路径


题意：求树上相距最长的两点间的距离。

思路：由于是无向图，每个点都可以当做是树根，因此，随便选一点作为起点，记录父节点保证向下遍历，获得的最长和次长的离树根的距离便是最长距离。

难点：题目有两个较难理解的地方，可以画图来理解

① 边权为负数的情况

如果离树根为负数，舍弃之，如果所有边权皆为负数，答案为零

② 如果最长距离不经过当前根的情况

当前根向下遍历，其可以遍历到整棵树，如果该根不经过最大距离，那么肯定是其子树上的某一点，由于为其子树，所以无法再遍历到该点，但正因为该点不为最大距离上的点，因此也没有必要遍历到，反之，该点一定可以作为最大路径上的根节点而得到最大路径。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 10010,M = N * 2;

#define x first
#define y second
typedef pair<int,int>p;
typedef long long ll;
int n;
int h[N],e[M],w[M],ne[M],idx;
int ans;

void add(int a,int b,int c){
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}

int dfs(int u,int father){
	int dist = 0;
	int d1 = 0,d2 = 0;
	for(int i=h[u];i!=-1;i = ne[i]){
		int j = e[i];
		if(j == father) continue;
		int d = dfs(j,u) + w[i];
		dist = max(dist,d);
		if(d >= d1) d2 = d1,d1 = d;
		else if(d > d2)  d2 = d;
 	}
 	ans = d1 + d2;
 	return dist;
}

int main(){
    cin >> n;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;++i){
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c),add(b,a,c);
	}
	dfs(1,-1);
	cout<<ans<<endl;
	return 0;
}