牛客 – 王国(虚树+树的直径)

题目链接:点击查看 题目大意:给出 n 个点组成的一棵树,每个节点都有一个权值,现在规定权值相同的节点之间,简单路径的边数为 x ,求 x * x 的最大值 题目分析:真的很巧,上周刚学的虚树,读完这个题的第一反应就是可以用虚树简化题目,其实完全可以用树形dp跑一遍dfs出来,可奈何我dp不好,就只能用虚树来做了 题目中有两个点可以单独考虑,首先是权值相同的点,这个就可以用虚树将权值相同的点都拎出来,然后是简单路径的边数最大,这个对应着树的直径,所以直接虚树配合树的直径写一个dfs,直接维护最大值就好了 代码: #include #include #include #include #i