[HDU2196]Computer（DP）

传送门

题意

给出一棵树，求离每个节点最远的点的距离

思路

对于我这种菜鸡，真是难啊。

每个点的距离它最远的点，除了在它子树中的，还有在它子树之外的，所以这几个状态都得表示出来。

我们能够很简单的求出每个点到以它为根的子树的最远点的距离，dfs 即可。

设 f[i][0] 表示点 i 到以它为根的子树的最远点的距离

　 f[i][1] 表示点 i 到以它为根的子树（并且这个子树与最远点所在子树不相同）的次远点的距离（一会会用到）

　 f[i][2] 表示 除去点 i 的子树后，点 i到离它最远的点的距离

　val 表示边权

那么 f[v][2] 怎么求？（u 表示 v 的父亲）

　　if(f[v][0] + val[i] == f[u][0]) f[v][2] = f[u][1] + val[i];

　　else f[v][2] = f[u][0] + val[i];

　　f[v][2] = std::max(f[v][2], f[u][2] + val[i]);

那么一个点 i 到它的最远点的距离即为——max( f[i][0], f[i][2])

代码

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define M(a, x) memset(a, x, sizeof(a)); 5 6 const int MAXN = 10005; 7 int n, cnt; 8 int head[MAXN], to[MAXN << 1], val[MAXN << 1], next[MAXN << 1], f[MAXN][3]; 9 bool vis[MAXN]; 10 11 inline void add(int x, int y, int z) 12 18 19 inline void dfs1(int u) 20 32 } 33 f[u][0] = dis1; 34 f[u][1] = dis2; 35 } 36 37 inline void dfs2(int u) 38 51 } 52 } 53 54 int main() 55 68 M(vis, 0); 69 dfs1(1); 70 M(vis, 0); 71 dfs2(1); 72 for(i = 1; i <= n; i++) printf("%d\n", std::max(f[i][0], f[i][2])); 73 } 74 return 0; 75 }
View Code

2017.6.18

重新复习了一遍，感觉理解更透彻了。

其中发现原来理解错了，有的地方写的不对，已改正。

上一篇：[POJ3041] Asteroids（最小点覆盖-匈牙利算法）

下一篇：[luoguP2564] [SCOI2009]生日礼物（队列）

---

DP