标签:动态规划-树形DP

DarkBzoj提交地址题意有 $N(\le 2000)$ 个农民, 他们住在 $N$ 个不同的村子里. 这 $N$ 个村子形成一棵树。每个农民初始时获得 $X$ 的钱。每一次操作, 一个农民可以从它自己的钱中, 取出任意数量的钱, 交给某个相邻村子的农民。对于每个农民给定一个值 $v_i$, 求:最少需要多少次操作, 使得每个农民最终拿到的钱 $\geq$ 给定的值。题解有个结论:每条边最...
题解 动态规划 动态规划-树形DP
DarkBzoj提交地址:因为没有SPJ,所以需要特殊处理答案如下:if (ans) printf("%.10f",ans); else puts("0");题意某个公司有 $n(\le 5\times 10^5)$ 个人, 上下级关系构成了一个有根树,其中有个人是叛徒(这个人不知道是谁)。对于一个人, 如果他下属(直接或者间接, 不包括他自己)中叛徒...
题解 动态规划 动态规划-树形DP
题意在一棵 $N$ 个点的树上放 $K$ 个监听器,每个监听器可以监听与它直接相连的节点,但不能监听自己。要求所有节点都被监听,求方案数。$N\le 100000 \ , \ K\le 100$ 。题解真·毒瘤题目。用 $f[x][i][0/1][0/1]$ 表示以 $x$ 节点为根的子树中除了 $x$ 都被监听了,放了 $i$ 个监听器,$x$ 上放没放监听器,$x$ 有没有被监听到 的方...
题解 动态规划 动态规划-树形DP
NOI/NOI+/CTSC
题意将一棵 $N$ 个点的树上 $K$ 个点染黑,另外的点染白。求黑点两两之间距离和加上白点两两之间距离和的最大值。$N,K\le 2000$ 。题解考虑每一条边的贡献,即为 边权 $\times ($ 一侧的黑点个数 $\times$ 另一侧的黑点个数 $+$ 一侧的白点个数 $\times$ 另一侧的白点个数 $)$ 。用 $f[x][i]$ 表示以 $x$ 为根的子树,黑点有 $i$ ...
题解 动态规划 动态规划-树形DP
省选/NOI-
庆祝第100篇文章完成!题意一棵有边权的树,有的节点是转播站,有的节点是用户节点。要让用户看到电视,代价为根节点到当前用户节点的路径和,重复的路径不重新计算。每个用户可以支付一定的钱。求在不亏本的情况下,最多可以让多少个用户看到电视。其中点数 $N\le 3000$ 。题解树上背包的裸题。用 $f[x][i]$ 表示在以 $x$ 节点为根的子树中选 $i$ 个用户的最大收益。转移方程式为:$...
题解 动态规划-树形DP
提高+/省选-
题意在树上放一些山贼集团的分部,每个分部可以收取根节点到它路径上所有节点的保护费。在节点 $i$ 建立分部 $j$ 花费 $s[i][j]$ 。对于每一个节点,如果它被多个分部收保护费,就可能产生收益或损失。求最优的放置方法,可以得到最大利润。其中点数 $N\le 100$ ,分部个数 $P\le 12$ 。题解看到 $P$ 的范围,显然可以对节点上放置分部的状态进行状压。因为每个分部收取的...
题解 动态规划-树形DP 动态规划-状压DP
省选/NOI-
题意求所有在树上直径的节点。点数 $N\le 200000$ 。题解我百度谷歌搜了一圈硬是没看到一个像样的题解,去提交记录里面看代码读懂的方法。先跑第一遍 $dfs$ ,记录以 $x$ 为根的子树中深度的最大值 $mx[x]$ 和次大值 $mx2[x]$ ,两者相加再 $+1$ 即为这个子树的直径。然后再跑一遍,对于每个节点 $x$ ,遍历所有子节点 $y$ ,并对子节点向上最大深度 $up...
题解 动态规划-树形DP
题意一棵无根树,要求根节点到每个叶子的路径上都至少有一个有色节点。给出根节点到每个叶子节点路径上最后一个有色节点的颜色,求有色节点个数最小值。其中点数 $N\le 1000$ ,叶子节点个数 $M\le 5021$ 。(我按个人习惯反过来了)题解树形dp,用 $f[x][0/1]$ 表示以 $x$ 为根的子树,最后一个有色节点颜色为黑/白的最优情况。考虑状态转移,如果子节点和自己要求一样,则...
题解 动态规划-树形DP
提高+/省选-
时隔半年再来做发现还是不会,于是乎还是写个总结吧。题意一棵二叉树,只能保留 $Q$ 条边,求剩下的边最大边权和。其中点数 $N\le 100$ ,$Q\le 100$ 。题解用 $f[x][j]$ 表示在以 $x$ 为根的子树上保留 $j$ 条边的最优情况。搜索时枚举 $x$ 的子节点 $y$ ,然后类比背包枚举以 $y$ 为根的子树保留的边数 $k$ ,得到状态转移如下:$f[x][j]=...
题解 动态规划-树形DP
提高+/省选-
又是一道我看了题解才知道怎么做的题,我还是太弱了。题意每个骑士都有一个自己痛恨的骑士(不会恨自己),这俩不能在一起,每个骑士有个能力值,问怎么组合使总的能力值最大。其中骑士的人数 $N\le 10^{6}$ 。题解分(看)析(题)题(解)目可以发现,如果将每个关系之间连一个双向边,每个连通块都有且仅有一个环,所以整个图就是一个基环森林,然后拆一条边分成两棵树各跑一遍树形dp即可。拆开看以后也...
题解 动态规划-树形DP
省选/NOI-
重题,双倍经验。https://llf0703.com/p/uva-1292.html而且uva的题还有多组输出,删掉就行了。struct Edge{ int next,to; } edge[3005]; int head[1505],n,m,a,b,c,cnt,f[1505][2],out[1505]; inline void add(int u,int v) { edg...
题解 动态规划-树形DP
提高+/省选-
跟舞会那道题差不多,如果父节点没有取那么所有子节点都必须取;如果父节点取了,子节点取或不取皆可。$$\begin{cases} f[i][1]=\sum \min(f[j][0],f[j][1]) \\ f[i][0]=\sum f[j][1] \end{cases}$$需要注意的是题目中已经把子树说明了,这就意味着只能有一个点作为根节点,所以应该连单向边,并且事先找到那个点作为根节点。st...
题解 动态规划-树形DP
提高+/省选-
大水题,题意就跟题目名一样,决策就是对于节点 $x$ 是否取当前搜到的儿子 $y$ ,显然要当前子树和要大于0我们才会取,然后dfs即可。方程式:$$f[x]+=max(f[y],0)$$struct Edge{ int next,to; } edge[32005]; int s[16005],n,m,a,b,c,cnt,head[16005],w[16005],ans; inli...
题解 动态规划-树形DP
普及+/提高
题意要从 $N$ 门课中选出 $M$ 门,有的课有价值和先决条件,求价值总和最大值。其中 $N,M\le 300$ 。题解1.多叉转二叉我们用 $f[x][cnt]$ 表示当前x节点,在以 $x$ 为根的子树中选 $cnt$ 个节点。对于每一个节点,可以有选和不选两个选项,如果不选就把 $cnt$ 全都给兄弟节点,也就是右节点;如果要选就把 $cnt$ 分别分配给 $x$ 的兄弟和以 $x$...
题解 算法-多叉树转二叉树 动态规划-树形DP
提高+/省选-
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划49 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP14 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP2 图论4 图论-LCA3 图论-Tarjan9 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束3 图论-强连通分量1 图论-最小环1 图论-最小生成树6 图论-最短/最长路17 图论-树上差分2 图论-桥1 图论-缩点4 图论-负环3 字符串3 字符串-kmp2 思维题3 数学25 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-栈1 数据结构-树状数组3 数据结构-树链剖分10 数据结构-线段树3 数据结构-队列1 比赛-Codeforces17 比赛-JX Round1 比赛-NOIp/CSP4 算法-二分/三分11 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希1 算法-多叉树转二叉树2 算法-差分3 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索20 算法-模拟5 算法-状态压缩4 算法-贪心8 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2