历届试题 大臣的旅费 树形DP

      题目链接：大臣的旅费

    思路：锦囊说用广搜，可惜这题没说数据范围，担心复杂度太高，我就直接用的树形DP--求树的最远路径。

    以城市1为整棵树的根结点，d(i)表示以i为根结点的子树的最远路径，还有一个f(i)表示以i为根结点，从根节点i出发的最远距离，状态转移方程d(i) = max1 + max2，或则d(i) = max，即选取最长的两条子树的最远路径相加，或只有一个子节点就是加上最大值。f(i) = max(len(i, j) + f(j));

AC代码：

#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#include <utility>#include <string>#include <iostream>#include <map>#include <set>#include <vector>#include <queue>#include <stack>using namespace std;#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int> const int maxn = 1e4 + 5;vector<PI>son[maxn];int d[maxn];bool cmp(int a, int b) {	return a > b;}int dfs(int u, int PRe) {	int n = son[u].size();	d[u] = 0;	int ans = 0;	vector<int>road;	if(!n) return 0;	for(int i = 0; i < n; ++i) {		int v = son[u][i].first, cost = son[u][i].second;		if(v == pre) continue;		int h = dfs(v, u);		ans =max(ans, h + cost);		road.push_back(h + cost);	}	sort(road.begin(), road.end(), cmp);	if(road.size() == 1) d[u] = road[0];	else if(road.size() > 1)d[u] = road[0] + road[1];	return ans;}int main() {	int n;	while(scanf("%d", &n) == 1) {		memset(d, 0, sizeof(d));		for(int i = 0; i < n; ++i) son[i].clear();		int x, y, cost;		for(int i = 1; i < n; ++i) {			scanf("%d%d%d", &x, &y, &cost);			son[x-1].push_back(make_pair(y-1, cost));			son[y-1].push_back(make_pair(x-1, cost));		}		dfs(0, -1);		int ans = 0;		for(int i = 0; i < n; ++i) {			ans = max(ans, d[i]);		}		printf("%d/n", (ans + 1)*ans/2 + ans * 10);	}	return 0;}如有不当之处欢迎指出！