搜索结果
查询Tags标签： 换根，共有 7条记录-
CF718D Andrew and Chemistry
给你一个有 \(n\) 个点的树。当每一个点的度不超过 \(4\) 时这棵树是合法的。现在让你再添加一个点，在树仍然合法的情况下，一共有多少种树。 当两棵树同构时视作同一种。 保证输入的树是合法的。 \(n \le 10^5\)换根 DP 动态规划 树哈希学习 xzz 的树哈希做法。考虑将新…
2022/2/14 23:18:44 人评论 次浏览 -
[oiclass2478] Kamp：树形DP+换根+最长链
题意 一颗树 \(n\) 个点，\(n-1\) 条边，经过每条边都要花费一定的时间，任意两个点都是联通的。 有 \(K\) 个人（分布在 \(K\) 个不同的点）要集中到一个点举行聚会。 聚会结束后需要一辆车从举行聚会的这点出发，把这 \(K\) 个人分别送回去。 请你回答，对于 \(i=1\sim …
2022/1/8 23:04:23 人评论 次浏览 -
[oiclass2478] Kamp：树形DP+换根+最长链
题意 一颗树 \(n\) 个点，\(n-1\) 条边，经过每条边都要花费一定的时间，任意两个点都是联通的。 有 \(K\) 个人（分布在 \(K\) 个不同的点）要集中到一个点举行聚会。 聚会结束后需要一辆车从举行聚会的这点出发，把这 \(K\) 个人分别送回去。 请你回答，对于 \(i=1\sim …
2022/1/8 23:04:23 人评论 次浏览 -
【洛谷P3647】[APIO2014]连珠线
传送门 前言 对于换根的理解应该和其他题解不一样，求过。 题解 首先分析题目简化题意：给定一棵树，从里面选出若干个“三连点”的边，使边权和最大。其中“三连边”有如下图两种形态：\(3-1-2\) 和 \(3-5-6\)（图源：tommymio） 一开始我想到一种 DP：\(dp(u,0/1/2)\) 表…
2021/10/27 23:13:39 人评论 次浏览 -
【洛谷P3647】[APIO2014]连珠线
传送门 前言 对于换根的理解应该和其他题解不一样，求过。 题解 首先分析题目简化题意：给定一棵树，从里面选出若干个“三连点”的边，使边权和最大。其中“三连边”有如下图两种形态：\(3-1-2\) 和 \(3-5-6\)（图源：tommymio） 一开始我想到一种 DP：\(dp(u,0/1/2)\) 表…
2021/10/27 23:13:39 人评论 次浏览 -
CF219D题解
题面 一道看上去像道换根DP但可以用其他方法水过去的题目，正解显然是换根DP。 考虑换根DP两个步骤，一个是求 \(f_1\) ，第二是由 \(f_u\) 推出 \(f_v\) 。 先是状态的定义。 \(f_i\) 表示以 \(i\) 为根的答案。 然后考虑"反向边"怎么存，因为不能不存。这个可…
2021/8/13 6:06:01 人评论 次浏览 -
CF219D题解
题面 一道看上去像道换根DP但可以用其他方法水过去的题目，正解显然是换根DP。 考虑换根DP两个步骤，一个是求 \(f_1\) ，第二是由 \(f_u\) 推出 \(f_v\) 。 先是状态的定义。 \(f_i\) 表示以 \(i\) 为根的答案。 然后考虑"反向边"怎么存，因为不能不存。这个可…
2021/8/13 6:06:01 人评论 次浏览
