求树上最长链（或者说树的直径、树上距离最远的两点距离，树中所有最短路径距离的最大值qwq）的模板题，网上讲解很多，注意点权有负数即可 参考资料1(by ROCKYONE) 参考资料2(by forever_dreams) 1.树形DP（可以有效处理负边权）2.两次dfs或bfs（无法处理负边权）
展开全文
树上子链 题目地址： https://ac.nowcoder.com/acm/problem/202475 基本思路： 基本上类似树的直径的求法,我们每次找子树中的次长链和最长链相连取最大就是了,注意由于有负数的情况,可能取了次长链反而更不优,所以要再对只取最长链的情况多取一个，其余地方就和
展开全文
思路分析： 1.题目要求求解点权之和，这里区别一下点权和边权2.求最大的子链：就是树的直径 = ｍａｘ（最长链+次长链）3.因为有负权，所以不能使用BFS或DFS 参考代码： #include<bits/stdc++.h>
using namespace std;
const int
展开全文
这题非求直径, 而是求树上最大的连续的片段 -给定一棵树 T ，树 T 上每个点都有一个权值。 - 定义一颗树的子链的大小为：这个子链上所有结点的权值和 。 - 请在树 T 中找出一条最大的子链并输出。 Face tutorial:常规dfs, dp[i]代表该子树中最大的一条链(由
展开全文
思路 对于一个起始点x，最大子链是从x开始或者从x的子节点开始的最大子链。答案是从x作为起始点得到的最大子链的最大值，起点在dfs过程中走一遍就不会超时了。然后就是树形dp的问题啦。坑点:要开ll，同时注意所有点权值都为负数的情况。 代码 #include<bits/stdc++.h>
展开全文
本题的树上子链的说法是我第一次见，树上子链指的是树上的任意一条链，换句话说就是树上任意两点中最长的那一个。但这题不是以长度定的，每个节点都有权值，要的是权值和最长的子链。
所以我们对于某一个节点，选取儿子中最长和次长。然后加上节点本身就是答案了。
但在这里面寻找最长和次长的方式很巧妙，先
展开全文
刚学树形dp表示WA哭了，调了半天才调出来。 树的直径：对于一颗n个结点的无根树，找到一条最长路径，也就是找到两个点，让他们的距离最远。学习树形dp之前，有一个操作，就是通过第一次dfs找到一个最深叶子结点，再通过这个点为根，去找另一个最深的叶子结点，就完成了最长链的操作，这个方法虽然简单，但是不够
展开全文
思路：dp[i]表示以i为根节点的子链最大值是多少，u为根时，v为u的子节点，我们可以让u和v两条链相连可得，res=max(res,dp[u]+dp[v])，在dfs的时候不断合并两条链取最大值，然后我们再更新此时u这条链，dp[u]=max(dp[u]，a[u]+dp[v])，因为可能全为负数所
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
