HBC236124[SHOI2014]超能粒子炮,枚举,卢卡斯定理礼物题解

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

ZHR 要给一个重要的人送礼物，但是他情商特别低，所以只好出道题送给这个人， 这道题目以一棵有根树作为输入，ZHR 当然希望这道题数据强一点，这样才显得不敷衍，现在他想让一种错解被卡掉，假设树上有 nnn 个节点，编号为 111 到 nnn，那么这个错解的运行时间为 ∑i=1n∑j=1nLCA(i,j)sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}text

ZHR 要给一个重要的人送礼物，但是他情商特别低，所以只好出道题送给这个人。 这道题目以一棵有根树作为输入。ZHR 当然希望这道题数据强一点，这样才显得不敷衍。现在他想让一种错解被卡掉。假设树上有 nnn 个节点，编号为 111 到 nnn，那么这个错解的运行时间为 ∑i=1n∑j=1nLCA(i,j)sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}text{LCA}(i,j)i=1∑n​j=1∑n​LCA(i,j) 其中 LCA(i,j)text{LCA}(i,j)LCA(i,j)指编号为 iii 和编号为 jjj 的节点的最近公共祖先的编号。 现在 ZHR 把他生成的一个无根树给你，他希望你找到一个节点作为根使得错解的运行时间最大，请你输出错解的运行时间和找到的根。

不断挑战自我，才能突破极限！全网最全C++题库，让您在编程道路上越走越远。

标签： HBC236124[SHOI2014]超能粒子炮 枚举 卢卡斯定理礼物题解