点分治模板

poj 1741

1.选取一个点,把无根树变成有根树。通过树形dp的方式选择。用son记录点的子树大小,用F算出最大的子树,当F[x]<F[root]时,更换root.

2.再次通过dfs处理树上的deep和距离。

3.处理连通块中通过根节点的路径。减去同一子树内部的路径。

4.递归。

bzoj 2152
同上模板,只需要计算dist%3==0的点对,用一个数组记录%3以后的距离。

Leave a Reply

Your email address will not be published. Required fields are marked *