[树上DP] POJ2631 树的最长路径（最远点对）

[树上DP] POJ2631 树的最长路径（最远点对）

题目

对于一棵n个结点的无根树，找到一条最长路径。换句话说，要找到两个点，使得它们的距离最远。
POJ2631

思路

和树的重心问题一样，先把无根树转成有根树。对于任意结点i，经过i的最长路就连接i的两棵不同子树u和v的最深叶子的路径。

基本的求法是，先随便找一个点作为根结点转换为无根树后，遍历每一个点，找出当i为根结点时的子树到叶子的最大距离d(j)，在根据d(j)求出结点i作为根结点时整个树的最长路径，维护最长路径即可。


1.状态定义：d(i)，i为根结点的子树到叶子的最大距离。
2.状态转移方程：

d(i)=max{d(j)+1} d ( i ) = m a x { d ( j ) + 1 } $$d(i) = maxleft{d(j) + 1right}$$


POJ2631因为边有了权值所以略有不同，状态转移方程改成这样即可：
d(i)=max{d(j)+w(i)} d ( i ) = m a x { d ( j ) + w ( i ) } $$d(i) = maxleft{d(j) + w(i)right}$$

代码

POJ2631

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <utility>
#include <algorithm>
#define _for(i,a,b) for(int i = (a); i<(b); i++)
#define _rep(i,a,b) for(int i = (a); i<=(b); i++)
using namespace std;const int maxn = 10000 + 100;
vector< pair<int, int> > edges[maxn];
int n, d[maxn];int solve(int i, int r) {d[i] = 0;int max1 = 0, max2 = 0;for(vector< pair<int, int> >::iterator iter = edges[i].begin(); iter != edges[i].end(); ++iter)if ((*iter).first != r) {solve((*iter).first, i);if (d[(*iter).first] + (*iter).second > max1) {max2 = max1;max1 = d[(*iter).first] + (*iter).second;}else if (d[(*iter).first] + (*iter).second > max2) {max2 = d[(*iter).first] + (*iter).second;}}d[i] = max1;return max1 + max2;
}int main() {int u, v, w;while (scanf("%d%d%d", &u, &v, &w) == 3) {edges[u].push_back(make_pair(v, w));edges[v].push_back(make_pair(u, w));}int ans = solve(1, 0);  // 将1作为根结点printf("%dn", ans);return 0;
}