算法合集之《分治算法在树的路径问题中的应用》.pdf

《算法合集之《分治算法在树的路径问题中的应用》.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IOI2009中国国家集训队论文长沙市雅礼中学漆子超分治算法在树的路径问题中的应用【摘要】树作为一类特殊的数据结构，在信息学中有着极为重要的作用，各类关于树的题目在竞赛中更是屡见不鲜。本文选取了近几年出现的关于树的路径的题目，并结合例题讲解了分治算法在此类问题上的应用。【关键字】树路径路径剖分分治数据结构1IOI2009中国国家集训队论文长沙市雅礼中学漆子超【目录】【序言】........................................................................

2、................................................3【正文】........................................................................................................................4一.树的分治算法..............................................................................

3、......................4基于点的分治：..............................................................................................4基于边的分治：..............................................................................................4效率分析：............................

4、..........................................................................5【例1】树中点对统计...................................................................................8算法分析.......................................................................................

5、............8【例2】FreeTour2......................................................................................10算法分析.................................................................................................10【本节小结】.....................................

6、...........................................................13二．树的路径剖分算法：...................................................................................14【例3】QueryOnaTree..............................................................................14算法分析...

7、..............................................................................................14引入路径剖分.........................................................................................14轻重边路径剖分............................................................

8、.........................15【例4】黑白树...........................................................................................17算法分析.................................................