Tree(点分治)

2017年10月29日340

Tree

对问题的分析设计过程

该题要求求出树上路径长度$\leq K$的路径总数,为点分治经典题目

程序中用到的数据机构和算法

程序使用点分治实现,点分治的思想为将一颗树通过重心分割成多棵树来分治求解。即答案=路径通过重心的合法数目+子树答案。求解路径通过重心的合法数目可以通过容斥原理在$O(n\log n)$的时间内得出,可以证明,在用重心进行分割的前提下,时间复杂度为$O(n\log^2 n)$

程序的运行情况

该程序提交了两次才通过,具体情况如下:

321509264477_.pic

311509264471_.pic

在实习过程中得到的经验和体会

要对程序的初始值有足够的细心

Code:

 

%d 博主赞过: