18duangduang

题解

未归档(23) 计算几何(1)

/ 注册

全部文章 / 题解（共2篇）

牛客IOI周赛16-普及组 D. 杀树

题意：给定一棵树,第i个结点有权值,删除一些结点的代价是删除结点的权值和,求满足树上任何一条链长度小于等于l的删除方案代价最小.(n<=5000, <=5000 )分析: 从n的范围可以知道复杂度可以是n^2,那么可以搞树形二维dp. 表示以第i个结点为根节点的子树满足最长链小于等于...

树形dp

2020-05-02

4 568

牛客练习赛62 C.牛牛染颜色

题意：牛牛最近得到了一颗树，根是 1 号节点，他想要把这颗树染色。每个节点可以染成白色和黑色，牛牛认为一种染色方案是好的当且仅当任意两个黑点的 lca（最近公共祖先）的颜色也是黑色的。求一共有多少种好的染色的方案。答案 mod(1e9+7).分析：树形dp.考虑当前节点为根节点的子树方案数，dp...

树形dp lca

2020-04-25

0 860