首页 > 孤独的树
开通博客写题解
头像 Suzt_ilymtics
发表于 2022-04-22 21:07:28
对于每种质因子取出包含这个质因子的点的导出子图，这个子图一定是一个森林，现在要做的是删除森林中的若干个节点，使得没有任意两个节点之间有边相连，删除节点的代价是这个质因子的指数，这个直接对每棵树做一遍简单树形dp即可。 由于每个数最多包含 O(log⁡vali)O(\log val_i)O(logva 展开全文
去ta的博客 赞 (6) 回复(4) 收起
头像 wust芦智文
发表于 2022-04-26 15:34:18
题意分析： 给出一棵树，对于该树上的每个节点都有自己的权值，然后可以通过对某个权值进行除以他的质因子值的操作，求最少的操作次数，能使整棵树相邻的两个节点的权值公约数都为1； 个人思路 ： 首先，众所周知，小白月赛最后一题只要是树，那都是树形dp(bushi),很容易想到定义dp为以i为根子树的节点的 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”