RK_little
RK_little
全部文章
题解
翻译(1)
归档
标签
去牛客网
登录
/
注册
rk$ blog
~ welcom ~
全部文章
/ 题解
(共8篇)
P5904 [POI2014]HOT-Hotels 加强版
P5904 [POI2014]HOT-Hotels 加强版 题意 求在一个树内有多少个三元组(i,j,k)(i,j,k)(i,j,k)满足 dis(i,j)=dis(i,k)=dis(j,k)dis(i,j)=dis(i,k)=dis(j,k)dis(i,j)=dis(i,k)=dis(j,k) 思...
长链剖分
树形DP
2022-03-16
0
339
P3647 连珠线
P3647 连珠线 题解 题意 我们有 n 个珠子,我们可以选择一枚珠子作为我们的起点。然后我们可以选择用红线将新珠子与已有的珠子连起来,或者在用红线连起来的两个点间加入一个点,并将红线替换为两个蓝线。 蓝线的长度即为我们的分数,求最大得分。 思路 首先我们任意选取一个节点作为根。 那么一定会出现下...
树形DP
2022-02-20
0
316
CF708C Centroids 题解
CF708C Centroids 题解 可以选择在这里阅读 题意 你拥有一棵树,现在你又一次改造树的机会,即删去原来树中的一个边,并且加上一个边使得其依然为树。求问对于每个点而言,是否存在机会使得改造后的树其可以成为树的重心。 思路 我们如果想要求其改造后是否可以取得重心,因此我们对任意一个节点,我...
树形DP
2022-02-19
0
272
# CF1632 E2 Distance Tree (hard version)
Distance Tree (hard version) 可以在这个地方阅读 题意 你拥有一棵树,定义其根为 1 号节点,现在你有能力在这棵树中再添加一条边。使得这棵树的最长路径改变。现在你添加的这个边的边权从 1 - n 依次增大,求问,每次增大后加入一条边,使之最长路径的最短距离为多少 思路 首...
树形DP
贪心
2022-02-01
1
621
P3354 Riv 河流
P3354 Riv 河流 也可以选择在这里阅读 题意 有一个 n + 1 个节点的树,其中 0 号节点为根。每个节点上都有一些物品,每个边都有长度。现在所有的物品只能朝着根的方向前进,现在设置k节点作为终点。问所有物品的移动距离之和最小是多少。 思路 首先,如果我们要求解其最小花费,我们发现其情况...
树形DP
2022-01-31
0
326
P1272 重建道路
P1272 重建道路 题意 给出一颗有 n 个节点的树,求问分解出一个含有 p 个节点的子树最少需要删去多少条边。 思路 假设我们要以一个节点为根,那么我们不妨定义 f[i , j] 用以表示节点 i 包括其根形成了具有 j 个结点的子树。 那么对于一个节点 u,我们可以直接得到f[u ,1] 的值...
树形DP
2022-01-21
0
314
P2495 消耗战
P2495 消耗战 题意 我们有一个树,它的根节点为 1 ,它的每条边都有相应的权值,我们每次都会产生一些点,要求如果要将这些点通过删边的方式使之不与根节点相连,求删去边权和的最小值。 思路 暴力 如何暴力做? 设 f[i] 表示所有的处理完这点的最小值 第一步,当我们输入我们所有的点之后,我们将所...
虚树
树形DP
2022-01-19
0
391
P2607 骑士
P2607 骑士 题意 有 nnn 个点,第 iii 个点连着 aia_iai 点。其中每个点都有一个权值。对于每条边而言,其两端的点不可以同时加入总和。我们要求总和最大值。 思路 可以借鉴之前的blog 首先,这个图可以看出是一个个基环数组成。我们要求的就是所有基环数的总和最大值的和。 对于一个...
基环树
树形DP
2022-01-18
0
334