传送门
题意
给出一棵树，求离每个节点最远的点的距离
思路
对于我这种菜鸡，真是难啊。
每个点的距离它最远的点，除了在它子树中的，还有在它子树之外的，所以这几个状态都得表示出来。
我们能够很简单的求出每个点到以它为根的子树的最远点的距离，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
重新复习了一遍，感觉理解更透彻了。
其中发现原来理解错了，有的地方写的不对，已改正。
上一篇：[POJ3233] Matrix Power Series（矩阵快速幂）
下一篇：[luoguP2564] [SCOI2009]生日礼物（队列）
DP
