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

这题有没有人写的O(n*sqrt(n)*logn)的DFS序递推，我优化半天死活TLE

Posted by bg95 at 2012-01-28 12:38:43 on Problem 1741 
按照DFS序递推，时刻维护每个点到当前结点的距离
从u结点递推到v结点（v是u的孩子，uv间距离为d）时，v所在子树的到v的距离均比到u的距离减少d，其他结点的距离增加d。可以等价于把v所在子树距离减少2*d，其他结点不变，同时把k减少d。把所有结点按照DFS序排列，每次递推要修改一棵子树，一棵子树在DFS序中是一个区间。建立块状数组分块处理，一个块被全部修改则作修改标记，部分修改则暴力修改；把每个块内结点按到当前结点距离排序（修改时要维护有序），查询所有到当前结点距离不大于k的结点个数时，在每个块内二分查找。
时间复杂度不超过O(n*sqrt(n)*logn)，死活TLE……
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