本文主要是介绍HDU 2196 Computer（树形dp经典），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文出自 http://blog.csdn.net/shuangde800
题目传送门
题意：
给出一棵树，求离每个节点最远的点的距离
思路：
把无根树转化成有根树分析，
对于上面那棵树，要求距结点2的最长距离，那么，就需要知道以2为顶点的子树（蓝色圈起的部分，我们叫它Tree（2）），距顶点2的最远距离L1
还有知道2的父节点1为根节点的树Tree（1）-Tree(2)部分（即红色圈起部分），距离结点1的最长距离+dist(1,2) = L2，那么最终距离结点2最远的距离就是max{L1，L2}
f[i][0],表示顶点为i的子树的，距顶点i的最长距离
f[i][1],表示Tree(i的父节点)-Tree(i)的最长距离+i跟i的父节点距离
要求所有的f[i][0]很简单，只要先做一次dfs求每个结点到叶子结点的最长距离即可。
然后要求f[i][1], 可以从父节点递推到子节点，
假设节点u有n个子节点，分别是v1,v2...vn
那么
如果vi不是u最长距离经过的节点，f[vi][1] = dist(vi,u)+max(f[u][0], f[u][1])
如果vi是u最长距离经过的节点，那么不能选择f[u][0],因为这保存的就是最长距离，要选择Tree（u）第二大距离secondDist,
可得f[vi][1] = dist(vi, u) + max(secondDist, f[u][1])
代码：
/**==========================================* This is a solution for ACM/ICPC problem** @author: shuangde* @blog: blog.csdn.net/shuangde800* @email: zengshuangde@gmail.com*===========================================*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;typedef long long int64;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);const int MAXN = 10010;struct Node{int v, w;
};vector<Node>adj[MAXN];int indeg[MAXN];
int val[MAXN];
int n, m;
int64 f[MAXN][2];
int vis[MAXN];int64 dfs1(int u){vis[u] = true;f[u][0] = 0;for(int i=0; i<adj[u].size(); ++i){int v = adj[u][i].v;int w = adj[u][i].w;if(vis[v]) continue;f[u][0] = max(f[u][0], dfs1(v)+w);}return f[u][0];
}void dfs2(int u, int fa_w){vis[u] = true;int max1=0, v1, max2=0, v2;for(int i=0; i<adj[u].size(); ++i){int v = adj[u][i].v;int w = adj[u][i].w;if(vis[v]) continue;int tmp = f[v][0] + w;if(tmp > max1){max2 = max1; v2 = v1;max1 = tmp; v1 = v;}else if(tmp == max1 || tmp>max2){max2 = tmp;v2 = v;}}if(u != 1){ int tmp = f[u][1];int v = -1;if(tmp > max1){max2 = max1; v2 = v1;max1 = tmp; v1 = v;}else if(tmp == max1 || tmp>max2){max2 = tmp;v2 = v;}}for(int i=0; i<adj[u].size(); ++i){int v = adj[u][i].v;int w = adj[u][i].w;if(vis[v]) continue;if(v==v1){f[v][1] = max2 + w;}else{f[v][1] = max1 + w; }dfs2(v, w);}
}int main(){while(~scanf("%d", &n) && n){for(int i=1; i<=n; ++i) adj[i].clear();for(int u=2; u<=n; ++u){int v, w;scanf("%d%d", &v, &w);adj[u].push_back((Node){v, w});adj[v].push_back((Node){u, w});}memset(f, 0, sizeof(f));memset(vis, 0, sizeof(vis));dfs1(1);memset(vis, 0, sizeof(vis));dfs2(1, 0);for(int i=1; i<=n; ++i){cout << max(f[i][0], f[i][1]) << endl;}}return 0;
}这篇关于HDU 2196 Computer（树形dp经典）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
