2021CCPC网络赛(重赛) 1011.Jumping monkey

本文主要是介绍2021CCPC网络赛(重赛) 1011.Jumping monkey，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目大意：给定一棵树，要求你求出对于每个节点，一只猴子从该节点开始跳，每次只能跳向到目标点最短路上权值最大的点为目标点的点，这样的点对于每个节点有多少个。

思路：考虑每个节点对其都无贡献的点，应该是所有点中权值最大的点，从该点出发无法跳向任何其他点。去除该点后，原来次大的节点同样无法向除去已去除点外的别的点跳。反复的执行这个过程，直至所有节点均被删去。但实际上这不好操作，因此我们考虑这个过程的逆过程：

首先将各个节点按照权值大小排序，从权值最小的节点开始遍历，每次将该节点作为上个节点以及已遍历过的邻接节点的父节点，这样便可以得到一棵新树，不难发现对于每个节点而言，其在新树上的深度即为所求答案(设根节点深度为 0 0 0)。

这篇关于2021CCPC网络赛(重赛) 1011.Jumping monkey的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！