GoldenPotato137的小屋

树形DP
动态规划

[Luogu P3233] [HNOI2014]世界树

题面 P3233 [HNOI2014]世界树 Solution 这是一道虚树妙题。 我们不妨先考虑一下每一次$O(n)$计算的暴力怎么做。 $O(n\cdot m)$的暴力肥肠简单,我们只需要做两遍dfs。考虑设$f[i]$表示离$i$最近的聚居地是什么,$MIN[i]$表示$i$到最近的聚居地的距离。我们第一遍dfs先找出$i$到它子树内的聚居地的最小距离,之后再做一遍dfs来找$i$往祖先方向后头走能走到的最近聚居地的距离即可。 观察数据范围后发现,$\sum m<=300000$,因此考虑使用虚树。 建…

2019年4月1日 0条评论 1005点热度 3人点赞 GoldenPotato137 阅读全文
动态规划

[Luogu P4297] [NOI2006]网络收费

题面 P4297 [NOI2006]网络收费 Solution 这题喵啊。 首先,我们会发现统计两个点互相的贡献是一个极其困难的问题。 但是,仔细观察那张收费表格后会发现,我们可以重新定义一下这个收费:我们假设路由器节点的颜色为叶子中数目较多的颜色,当一个叶子结点颜色与路由器节点颜色相同的时候不收钱,否则收一份钱。我们可以惊讶的发现,这样做之后我们的新收费做法就与原来题目要求的重合了,而且贡献由点对转到了点上。 接下来,我们就可以统计每个叶子节点对每个路由器产生的贡献了。我们设$F[i][j]$表示第$i$个叶子节…

2019年3月29日 0条评论 725点热度 1人点赞 GoldenPotato137 阅读全文
动态规划

[Luogu P4438] [HNOI/AHOI2018]道路

题面 4438 [HNOI/AHOI2018]道路 Solution 这是一道树形DP妙题。 平时,我们设计树形DP的状态一般都是以子树为基础来设计的。很不幸的是,这题因为那个蜜汁柿子无法化简,导致了极其严重的后效性。因此,我们这里并不能以子树为基础来设计状态了。 这题妙就妙在这个状态设计。这题我们考虑以链为基础来设计状态。 设$f[i][j][k]$表示从根节点到达第$i$个点,一路上经过了$j$条没有修过的公路及$k$条没有修过的铁路,把它的孩子全部连同到根所需的最小代价。 这样一来,我们惊讶的发现这样设就没有…

2019年3月28日 2条评论 1256点热度 0人点赞 GoldenPotato137 阅读全文
动态规划

[Luogu P2014]选课

题面 传送门:洛谷 Solution 这是一道十分经典的树形DP题,这种类型的树形DP有一种很普遍的解法。 首先,观察题目,我们把这道题转换一下:给定一颗树,选出包含1号节点(根)的一颗子树,使得点权和最大。 我们可以这样子定义状态: 设$f[i][j]$ 表示以i为根节点的子树,选出j个节点,所能达到的最大点权值。 对于二叉树来说,转移很显然,就是枚举左子树分配多少个节点,就可以对应的得出右子树能分配到多少个节点,对所有情况取最大值就好。 对于多叉树来说,问题就没有那么简单了,这里,我们有两个方案可以解决这个问题…

2019年2月22日 0条评论 631点热度 0人点赞 GoldenPotato137 阅读全文
动态规划

[Luogu P1122]最大子树和

题面 传送门:洛谷 Solution 这是一道简单的树形DP题。 首先,我们可以转换一下题面,可以发现,题目要求我们求出一颗树上的最大联通子图。 因为我们是在树上取的,实际上就是取一颗子树。 这个就是最基础的树形DP模型了。 我们可以设f[i]表示我们选的子图以i为根所能取的子树的最大值。 转移是: $f[i] = beauty[i] + xigema(max(f[j],0))$ (也就是一颗树的孩子所能取的子树,如果它孩子为根的子树>0,就取它,否则不取) 答案就是最大的$f[i]$ Code //Luogu P…

2019年2月22日 0条评论 760点热度 0人点赞 GoldenPotato137 阅读全文

GoldenPotato137

LLer/ACMer/HITer/数院菜鸡/ECS折磨中

最近评论
hilaolu 发布于 1 年前(03月16日) 球球屑gp翻我展示一下ua屑屑
Guava 发布于 1 年前(11月30日) @GoldenPotato137 暂时是 guavaoj.tk
碱式碳酸希 发布于 1 年前(11月30日) 可以先不要告诉老师们吗(偷偷搞的
碱式碳酸希 发布于 2 年前(11月04日) %%%%Tql 请求搬运至NNEZ校内OJ公告中。 展示链接: 请在启天楼内网中访问! :razz:...
630分苦苦挣扎的菜鸡土豆 发布于 2 年前(05月01日) 肥肠抱歉,刚刚看见呢。 那个发送留言不能立刻看见源于我站挂了个腾讯云cdn,默认会返缓存的内容qwq...
分类
  • CDQ分治
  • DAG DP
  • DP+DP
  • FFT/NTT
  • Kruskal重构树
  • LCT
  • LUCAS
  • NNEZ
  • set
  • splay
  • 主席树
  • 二分/二分答案
  • 位运算
  • 倍增
  • 其他
  • 分块
  • 动态规划
  • 卷积
  • 反演
  • 同余
  • 后缀数组
  • 后缀自动机
  • 哈希
  • 图论
  • 圆方树
  • 堆
  • 多项式
  • 字符串
  • 学习笔记
  • 容斥
  • 容斥
  • 左偏树
  • 并查集
  • 数位DP
  • 数学
  • 数据结构
  • 整体二分
  • 斯特林数
  • 最小割
  • 最短路径
  • 未分类
  • 树套树
  • 树形DP
  • 模拟
  • 深度学习
  • 游记/自闭记/滚粗记
  • 点分治
  • 状压DP
  • 生涯纪录
  • 线段树
  • 组合数学
  • 缩点/强连通分量
  • 网格DP
  • 网络最大流
  • 网络流
  • 背包DP
  • 虚树
  • 贪心
  • 边双/点双
归档
  • 2022年1月
  • 2021年9月
  • 2021年3月
  • 2021年2月
  • 2019年11月
  • 2019年4月
  • 2019年3月
  • 2019年2月

COPYRIGHT © 2022 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

桂ICP备20002051号