[tyvj1520] 树的直径

发表于   |  

描述

树的直径，即这棵树中距离最远的两个结点的距离。每两个相邻的结点的距离为1，即父亲结点与儿子结点或儿子结点与父子结点之间的距离为1.有趣的是，从树的任意一个结点a出发，走到距离最远的结点b，再从结点b出发，能够走的最远距离，就是树的直径。树中相邻两个结点的距离为1。你的任务是：给定一棵树，求这棵树中距离最远的两个结点的距离。

输入格式

输入共n行
第一行是一个正整数n，表示这棵树的结点数
接下来的n-1行，每行三个正整数a,b,w。表示结点a和结点b之间有一条边，长度为w
数据保证一定是一棵树，不必判错。

输出格式

输出共一行
第一行仅一个数，表示这棵树的最远距离
测试样例1

输入

4
1 2 10
1 3 12
1 4 15

输出

27

备注

10%的数据满足1<=n<=5
40%的数据满足1<=n<=100
100%的数据满足1<=n<=10000 1<=a,b<=n 1<=w<=10000

Solution

DP求最短路和次短路。（每个点看一下是不是最大）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
#define maxn 10000+1
#define maxm 20000+1
using namespace std;
int n, m, e;
int ans = 0;
int fir[maxn], nex[maxm];
int f1[maxn], f2[maxn];
struct data{
	int v, w;
}d[maxn];
void addedge(int u, int v, int w){
	d[++e].v = v;
	d[e].w = w;
	nex[e] = fir[u];
	fir[u] = e;
}
void dp(int u, int father){
	for (int i = fir[u]; i; i = nex[i]){
		int v = d[i].v, w = d[i].w;
		if (v == father) continue;
		dp(v, u);
		if (f1[v] + w > f1[u]){
			f2[u] = f1[u];
			f1[u] = f1[v] + w;
		} else f2[u] = max(f1[v] + w, f2[u]);
	}
	if (f1[u] + f2[u] > ans) ans = f1[u] + f2[u];
}
int main(){
	scanf(""%d"", &n);
	for (int i = 1; i <= n - 1; i++){
		int a, b, w;
		scanf(""%d%d%d"", &a, &b, &w);
		addedge(a, b, w);
		addedge(b, a, w);
	}
	dp(1, 0);
	printf(""%d\n"", ans);

}