C题：
gcd大于1时，mex不超过1;
mex大于1时，gcd为1；
因此答案要么来源于整个序列（mex最大化），要么来源于两个相邻数且其中一个为0（gcd最大化且mex为1）。
D题：
只考虑模2^20意义下的数，因此只有2^20个点，bfs预处理答案即可。
E题：
n<7时，答案为-1。
展开全文
G 魔法树
这题第一感觉就是树形DP
但是这里面的状态蛮多的，不太好下手。
其实可以分情况讨论
全是奇数
全是偶数
这样的话，dfs中需要维护的状态反而少了。
还有一点就是，这题的核心是边
也就是边的选择/不选决定了方案数
只有理解这点，才能理解下面的转移方程
全是奇数连通分量
每个
展开全文
计数类树形 DP 的常用思路之一为决策边，将点或点所在连通块状态放在主状态的附加维中。例如CF461B，NOIP2022 T3都可以用这个思路解决。
回到本题，决策边的提示已经挂脸上了，考虑状态设计：注意每个点所在的连通块可以通过是否和儿子连边从而和儿子合并成一个大连通块来改变奇偶性，但是答案中整体
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
