Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:为什么要记录次长QwQIn Reply To:为什么要记录次长QwQ Posted by:CuriousCat at 2016-08-27 13:19:15 其实主要是一个树形DP的思想: 如果我们要求树上深度最大的点到根节点的距离,那显然只需记录最长。 但是我们求树的直径,实际上是求树上到根节点最远的两个点到根节点的距离之和,也就是求到根节点最远和次远的两个点到根节点的距离之和,于是答案就是最远和次远相加。 同样,如果题目改成“求与根节点距离最远的三个点到根节点的距离之和最大”,那就要记录最远、次远、第三远三个值。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator