Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:为什么要记录次长QwQ

Posted by suncongbo at 2017-11-25 22:54:48 on Problem 2631
In Reply To:为什么要记录次长QwQ Posted by:CuriousCat at 2016-08-27 13:19:15
其实主要是一个树形DP的思想:
如果我们要求树上深度最大的点到根节点的距离,那显然只需记录最长。
但是我们求树的直径,实际上是求树上到根节点最远的两个点到根节点的距离之和,也就是求到根节点最远和次远的两个点到根节点的距离之和,于是答案就是最远和次远相加。
同样,如果题目改成“求与根节点距离最远的三个点到根节点的距离之和最大”,那就要记录最远、次远、第三远三个值。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator