fuzhiji

题解

/ 注册

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

kingdom------(dp)

我们先根据题意一步一步分析，由于只是给出树的节点个数，树可以由我们任意构造，我们假设n个节点取得答案最大的时候树长这样根节点root，连接着k个子树，k个子树大小分别为sum1,sum2.....sumk，有我们令ans[n]为n个节点的树所得的最优解root的“心腹”其实就是root的重儿子，我们...

dp

2020-07-10

10 1306

漂亮的公园——虚树+dp+lca

假设节点颜色为 ,对于求颜色在树上距离最大的两点，我们需要先找出树上颜色为的距离最大的两点，找出树上颜色为的距离最大的两点，然后枚举求不同颜色的两点距离，得到的最大值就是的最远距离。所以，我们只需要预处理出所有颜色的最远两点，然后计算的时候用LCA求距离即可。当然，颜色可能很多，多达种...

虚树树的直径 lca dp

2020-06-03

2 894