←_←

题目链接 题意 给你一颗树多次询问，每次询问若干个节点，求最少删除几个节点使得任意两选中节点不连通，询问总共的点集不超过 100000100000100000 思路 先建个虚树，然后树形DP。 dp[u][0]dp[u][0]dp[u][0] 子树上没有选中点与 uuu 连通的最小花费 dp[u][1]dp[u][1]dp[u][1] 子树上不超过一个选中点与 uuu 连通的最小花费 转移方程见代...

题目链接 题意 给你一颗树边权为1多次询问，每次询问若干个点，求任意两点之间距离之和，最远点对权值，最近点对权值 思路 询问很多，但是询问总共的点集不超过 200000020000002000000 可以对每次查询建虚树，得到一颗新树后树形dp。 dp[u][0] 表示 子树中的询问节点数量 dp[u][1] 表示 以u为根节点子树中询问节点到u的最近距离 dp[u][1] 表示 以u为根节点子树...

题目链接 题意 一个大小为 nnn 的树，每点权值 &lt;si,pi&gt;&lt;si,pi&gt;<si,pi>，恰好K个点，要求∑p∑s\frac{\sum{p}}{\sum{s}}∑s∑p​最大。 还要满足 f[u]f[u]f[u] 选了才能选 uuu 思路 01分数规划，二分枚举答案，∑p∑s&gt;=ans\frac{\sum{p}...

题目链接 题意 给你一棵树有n鸽节点，节点编号1-n，每个节点上有xi鸽饼干，每个节点上吃饼干吃一块需要pi时间 再给你每个节点的父亲，和经过这条边所花费时间 刚开始你在起点，两个人轮流进行以下步骤，你先手 你：移动到子节点，或者结束游戏并移动到根节点，选择性吃沿途饼干 对手：删一条你所在节点到儿子的边，或者什么都不做 你现在有T的时间求最多能吃多少饼干。 思路 从根节点开始深搜，对当前点求 当...

题目链接 题意 一棵树，要放置哨兵（只能放在节点上），求最少放置哨兵保证能监视到所有的边。 即最小点覆盖 思路 树形DP入门，记得之前第一次遇到这题是用二分图求最小点覆盖过的，学了树形DP思想后再来水一发 顺便庆祝一下第一次CF蓝名，虽然下场感觉就要掉 ಥ_ಥ 每点分两种状态选和不选，选的话需要额外+1 该点不选，肯定需要继承所有儿子的 选 该点选，继承所有儿子 选和不选的较小值，还要+...

题目链接 题意（这好像是中文题，不会别的语言=_=||） 思路 我们以0为根节点向外建树，以前置点为起点，该点为终点，该点价值为线的权值。 由于每个结点只有一个父节点，每点权值等价两点之间线上的权值。 第一组样例可以这样建图 dp[i][j] 表示 i结点选j个的最大权值。 由于可以在任意子节点选部分数列然后组合而成，比如一个复杂的树，某点选择四个，可以由许多不同子节点选择方式组合而成。这里可以...