[POJ1741]Tree(点分治)

发布于 2018-02-22  117 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[POJ1741]Tree(点分治)

Description

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.

Http

HDU

Tag

点分治

题目大意

给出一棵树,求其中路径长度不超过一个给定的数\(K\)的点对个数

解决思路

考虑点分治,每一层从当前根出发\(bfs\)求出深度,然后组合出所有不超过\(K\)的方案。但这样就会有不合法的情况,所以要减去不经过当前根的答案,再递归求解。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[POJ1741]Tree(点分治)


HNCJ OIer