首页 > 多彩的树
开通博客写题解
头像 sunrise__sunrise
发表于 2020-05-08 09:24:45
A、多彩的树 看到颜色最大只有10种，考虑枚举全部的颜色搭配，二进制枚举即可 我们选取二进制位是1的表示该颜色本轮被选取。例如1011->第一种第二种第四种颜色被选取，第三种没被选中。这样一重循环枚举颜色组合，再去遍历这种颜色组合下的全部节点，通过DFS跑出每个符合颜色要求的连通块节点数。我们 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 sunsetcolors
发表于 2020-05-05 22:17:44
A 多彩的树 题目地址： https://ac.nowcoder.com/acm/contest/5556/A 基本思路： 我们看这个K只有10，所以很容易想到状压，那么我们状压颜色，然后对于每种情况我们去找图中只包含这几种颜色的连通块，对于每个联通块，假如包含n个顶点，那么路径就有条，也就 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 苟且的狮子
发表于 2021-03-17 18:46:37
状压dp、容斥 首先我们要知道树的一个重要的特性：对于树来说，他的路径总和为: 刚开始我想换根dp。。。。还以为自己想到了一个新的方法。。。。打算先以1为根处理以每个节点为起点，到其子树中找路径能找到的路径和然后再通过找子结点和父节点的关系从而换根 但是，这里的路径，只是通过找子结点和父节点的关系 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”