点分治模板

poj 1741

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

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

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

4.递归。

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Foreignbill