题目1072. 树的最长路径题目描述给定一棵树树中包含 n 个结点编号1~n和 n−1 条无向边每条边都有一个权值。现在请你找到树中的一条最长路径。换句话说要找到一条路径使得路径两端的点的距离最远。注意路径中可以只包含一个点。输入格式第一行包含整数 n。接下来 n−1 行每行包含三个整数 ai,bi,ci表示点 ai 和 bi 之间存在一条权值为 ci 的边。输出格式输出一个整数表示树的最长路径的长度。数据范围1 ≤ n ≤ 10000 , 1 ≤ a i , b i ≤ n , − 10 5 ≤ c i ≤ 10 5 1≤n≤10000, 1≤a_i,b_i≤n, −10^5≤c_i≤10^51≤n≤10000,1≤ai,bi≤n,−105≤ci≤105时空限制1s / 64MB输入样例6 5 1 6 1 4 5 6 3 9 2 6 8 6 1 7输出样例22思路由于存在负边权所以不能用两次 DFS / BFS的方法。可以用树形DP。核心思路是枚举中间节点u即从任意一个点u出发, 找到距离该点最远的2条路径, 加起来就是结果。为了找到最长路径和次长路径我们先来看看路径的分类。经过该点u的路径有以下三种类型① 以u的子树中的某个节点为起点以u为终点的路径② 以u的子树中的某个节点为起点以u的子树中的另一个节点为终点的路径③ 以u的子树中的某个节点为起点以u的祖先节点为终点的路径其中③又可以看作是u的祖先节点的情况①。所以我们只需要考虑情况①和②。代码如下#includebits/stdc.husingnamespacestd;constintN1000010;typedefpairint,intPII;intn,f[N][2],ans;vectorPIIg[N];voiddfs(intu,intfa){for(inti0;ig[u].size();i){PII tg[u][i];intvt.first,wt.second;if(vfa)continue;dfs(v,u);if(f[v][0]wf[u][0])f[u][1]f[u][0],f[u][0]f[v][0]w;elseif(f[v][0]wf[u][1])f[u][1]f[v][0]w;}ansmax(ans,f[u][0]f[u][1]);}intmain(){cinn;for(inti1;in;i){inta,b,c;cinabc;g[a].push_back({b,c}),g[b].push_back({a,c});}dfs(1,-1);coutans;return0;}结果如下100分参考https://www.acwing.com/solution/content/63883/感谢铅笔大佬的题解
