首页
比赛
题库
课程
竞赛讨论区
登录
/
注册
去牛客
首页
>
树学
17条解析
开通博客写题解
⊙__⊙
发表于 2020-04-13 17:06:49
链接:https://ac.nowcoder.com/acm/problem/201400 题意: 给出连通图,由n个点和n-1条边构成,在树上选择一个结点作为根,使得以这个结点为根的所有结点的深度和最小。默认根的深度为0 样例:41 21 31 4 很显然以1为根,depth=1+1+1=3 是最
展开全文
ThinkofBlank
发表于 2020-04-13 09:33:21
一.题解 这道题又是一道换根dp板子题,代码结构与 Accumulation Degree 这道题基本一致,唯一不同的就是转移了【不过转移的时候,因为方程的原因不需要特殊考虑叶节点】 我们先套路的设表示以为根的子树中,所有点的深度和,现在,我们来想想转移。 我们发现,如
展开全文
塞蒙尘
发表于 2020-04-12 21:17:52
Solution 十分简单的换根dp。 首先随便选择一个点作为根,计算出它的结果; 考虑它的一个相邻结点作为根时的结果与之间的关系:当根从转移到时,子树内的点到根的距离减少、子树外的点到根的距离增加,如果设为以为根时的子树大小,那么。 按照式子暴力dfs转移即可,复杂度。 Code #include
展开全文
在刷题的单身狗很开心
发表于 2023-10-29 16:39:17
在树上进行操作的记忆化搜索,通过DFS加灵活换根的方式进行。 首先先走一遍DFS,得到每个节点下的深度和,节点的个数和(包括节点自身)。 然后让1成为根,那么再进行DFS下去的每一个节点都可以有一个动态规划递推式来快速计算得到加入某个节点为根的时候的深度和。 递推式为:dp[x]
展开全文
hnust_yangyanjun
发表于 2020-08-22 13:26:37
题意:给你一颗树,你选择一个节点当根,求所有点的深度和最少为多少? 思路:树状dp+换根一开始随便选一个点当根计算结果。dp[i]表示以i为根的子树节点的深度和。se[i]表示以i为根的子树的节点数目。换根:dp[v]=dp[u]+n-2*se[v];(v为u的子节点,根从u转向v时,以v为根的子树
展开全文
expect2004
发表于 2020-04-13 21:56:34
引言 对于树上的题目,一般都是在搜的过程中 解决。 其中 为搜索函数的复杂度。 题解 暴力 这道题有一个显然的 的暴力思路:就是枚举每一个点作为根,扫一遍。 换根DP 分析暴力做法的时间复杂度瓶颈,发现主要在于每次都要遍历整棵树。 考虑是否能够每次 地转移两个根之间的信息。 显然,想要
展开全文
Meul
发表于 2020-04-16 23:24:42
题意 一棵个结点的树,令根节点的深度,其他节点的深度为,求以某个点为根节点这棵树的最小为多少? 思路 我们要枚举每一个结点为根节点的为多少,我们可以先求得以某片叶子为根节点的,然后再找寻相连的的关系,记录最小值。以某一片叶子为根节点,DFS遍历整棵树,算其深度,算该节点的子树结点数量为。(无根树很多
展开全文
精神病科黄主任
发表于 2020-04-12 14:57:34
写两种做法吧。第一种是直接重心性质,第二种是树形dp+换根。 一、利用重心性质:下面是树的重心的性质:1.树中所有点到某个点的距离和中,到重心的距离和是最小的,如果有两个重心,他们的距离和一样。2.把两棵树通过一条边相连,新的树的重心在原来两棵树重心的连线上。3.一棵树添加或者删除一个节点,树的重心
展开全文
998244353
发表于 2020-04-17 15:33:38
题意: 给定一个点的树,求以其中哪个点为根时可使得所有点的深度最小。题解: 表示以为根的所有结点深度和。那么即答案。具体实现:初始可以随便指定一个点为根,然后求出以为根的所有点的深度,,然后遍历其所有的子结点,求出以子结点为根的深度和来更新最小深度,一次即可。求以子结点为根的深度和即将子结点拉成根,
展开全文
回归梦想
发表于 2020-04-14 22:34:07
@[TOC]传送 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 262144K,其他语言524288K64bit IO Format:> %lld 题目描述 牛妹有一张连通图,由n个点和n-1条边构成,也就是说这是一棵树,牛妹可以任意选择一个点为根,根的深度deproot
展开全文
查看本题
查看本题讨论
相关比赛
4479-牛客OI周赛14-普及组
进入比赛
18072-一起来做题~欢乐赛7
进入比赛
28260-牛客竞赛动态规划专题班树型dp练习
进入比赛
59977-【200题】算法基础精选题单
进入比赛
71358-西华师范大学团体程序设计天梯赛校内选拔赛
进入比赛
等你来战
查看全部
牛客小白月赛118
报名截止时间:2025-06-13 21:00
牛客周赛 Round 96
报名截止时间:2025-06-15 21:00
牛客练习赛141
报名截止时间:2025-06-20 21:30
第五届上海理工大学程序设计全国挑战赛
报名截止时间:2025-06-29 17:30
2025牛客暑期多校训练营1
报名截止时间:2025-07-15 17:00
2025牛客暑期多校训练营2
报名截止时间:2025-07-17 17:00
扫描二维码,关注牛客
意见反馈
下载牛客APP,随时随地刷题