题目大意
给出一棵树，其中每两个节点都可以形成一个路径（要求路径中的边只能走一次），求出所有路径中的长度最大值。
分析
树形结构，很容易想到递归，但为了节省时间，要考虑保存中间状态。于是，考虑使用记忆化搜索（也就是树形动态规划）。 保存状态 dp[i][2]，其中dp[i][0]表示以i为根的子树中路径的两个端点均不位于i的路径的最长值，dp[i][1]表示以i为根的子树中有一个端点位于i的路径的最长值。然后进行状态推演， dp[root][1] = 1 + max(dp[child][1]); dp[root][0] = max(max(max0, 2 + max1 + max2);(root的子节点数大于1） dp[root][0] = 1 + max1;(root的子节点数等于1） max0表示i的所有子节点中的最大的dp[c][0]， max1表示i的所有字节点中最大的dp[c][1], max2表示i的所有子节点中第二大的dp[c][1].
由于树的任何一个节点均可以作为根节点，因此dfs时候，选择1即可。
实现
#pragma once#pragma execution_character_set("utf-8")// 本文件为utf-8 编码格式#include #include #include using namespace std;#define N 100005int dp[N][2];struct Edge{ int to; int next;};Edge gEdges[2*N];int gHead[N];bool gVisited[N];int gEdgeIndex;void InsertEdge(int u, int v){ int e = gEdgeIndex++; gEdges[e].to = v; gEdges[e].next = gHead[u]; gHead[u] = e; e = gEdgeIndex++; gEdges[e].to = u; gEdges[e].next = gHead[v]; gHead[v] = e;}pair dfs(int root){ if (dp[root][0] != -1 && dp[root][1] != -1){ return pair (dp[root][0], dp[root][1]); } gVisited[root] = true; int e = gHead[root]; int max1 = 0, max2 = 0, max = 0, child_num = 0; for (; e != -1; e = gEdges[e].next){ int v = gEdges[e].to; if (!gVisited[v]){ pair result = dfs(v); max = max > result.first ? max : result.first; if (max1 >= result.second){ max2 = max2 > result.second ? max2 : result.second; } else{//求一组数中的第一大和第二大的数！！！ 注意次序 /* //这样做，在处理第一个result的时候， max1和max2赋值为同一个...error max1 = result.second; max2 = max1; //这样做，考虑到第一个值的处理，但是 对max1和max2的更新次序错了。 仔细考虑... max1 = result.second; if(max1 != 0) max2 = max1; */ if (max1 != 0) max2 = max1; max1 = result.second; } child_num++; } } if (child_num == 0) dp[root][0] = dp[root][1] = 0; else if (child_num == 1){ dp[root][0] = max; dp[root][1] = 1 + max1; } else{ dp[root][1] = 1 + max1; dp[root][0] = max > (2 + max1 + max2) ? max : (2 + max1 + max2); } return pair (dp[root][0], dp[root][1]);}void Init(){ memset(gVisited, false, sizeof(gVisited)); memset(gHead, -1, sizeof(gHead)); gEdgeIndex = 0; memset(gEdges, -1, sizeof(gEdges)); memset(dp, -1, sizeof(dp));}int main(){ int n, u, v; scanf("%d", &n); Init(); for (int i = 1; i < n; i++){ scanf("%d %d", &u, &v); InsertEdge(u, v); } pair result = dfs(1); printf("%d\n", result.first>result.second ? result.first : result.second); return 0;}