RK_little

题解

翻译(1)

/ 注册

全部文章 / 题解（共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 386

P3647 连珠线

P3647 连珠线题解题意我们有 n 个珠子，我们可以选择一枚珠子作为我们的起点。然后我们可以选择用红线将新珠子与已有的珠子连起来，或者在用红线连起来的两个点间加入一个点，并将红线替换为两个蓝线。蓝线的长度即为我们的分数，求最大得分。思路首先我们任意选取一个节点作为根。那么一定会出现下...

树形DP

2022-02-20

0 369

CF708C Centroids 题解

CF708C Centroids 题解可以选择在这里阅读题意你拥有一棵树，现在你又一次改造树的机会，即删去原来树中的一个边，并且加上一个边使得其依然为树。求问对于每个点而言，是否存在机会使得改造后的树其可以成为树的重心。思路我们如果想要求其改造后是否可以取得重心，因此我们对任意一个节点，我...

树形DP

2022-02-19

0 295

# CF1632 E2 Distance Tree (hard version)

Distance Tree (hard version) 可以在这个地方阅读题意你拥有一棵树，定义其根为 1 号节点，现在你有能力在这棵树中再添加一条边。使得这棵树的最长路径改变。现在你添加的这个边的边权从 1 - n 依次增大，求问，每次增大后加入一条边，使之最长路径的最短距离为多少思路首...

树形DP 贪心

2022-02-01

1 666

P3354 Riv 河流

P3354 Riv 河流也可以选择在这里阅读题意有一个 n + 1 个节点的树，其中 0 号节点为根。每个节点上都有一些物品，每个边都有长度。现在所有的物品只能朝着根的方向前进，现在设置k节点作为终点。问所有物品的移动距离之和最小是多少。思路首先，如果我们要求解其最小花费，我们发现其情况...

树形DP

2022-01-31

0 357

P1272 重建道路

P1272 重建道路题意给出一颗有 n 个节点的树，求问分解出一个含有 p 个节点的子树最少需要删去多少条边。思路假设我们要以一个节点为根，那么我们不妨定义 f[i , j] 用以表示节点 i 包括其根形成了具有 j 个结点的子树。那么对于一个节点 u，我们可以直接得到f[u ,1] 的值...

树形DP

2022-01-21

0 350

P2495 消耗战

P2495 消耗战题意我们有一个树，它的根节点为 1 ，它的每条边都有相应的权值，我们每次都会产生一些点，要求如果要将这些点通过删边的方式使之不与根节点相连，求删去边权和的最小值。思路暴力如何暴力做？设 f[i] 表示所有的处理完这点的最小值第一步，当我们输入我们所有的点之后，我们将所...

虚树树形DP

2022-01-19

0 428

P2607 骑士

P2607 骑士题意有 nnn 个点，第 iii 个点连着 aia_iai 点。其中每个点都有一个权值。对于每条边而言，其两端的点不可以同时加入总和。我们要求总和最大值。思路可以借鉴之前的blog 首先，这个图可以看出是一个个基环数组成。我们要求的就是所有基环数的总和最大值的和。对于一个...

基环树树形DP

2022-01-18

0 366