【POJ1741】Tree 树的点分治

题目链接:http://poj.org/problem?id=1741

原题描述

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.

Input

The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

Sample Output

题目大意

就是求一颗树中距离小于等于K的点对个数。。。

AC算法

点分治模板题。

大致思路是将路径分为经过重心和不经过重心两类,而不经过重心的路径可能经过子树的重心,于是在子树中解决同样的问题。

在计算过重心now的路径条数时,我们会统计以now为根的树中每一个点到now的距离,然后将距离和小于等于K的点对数记录下来。但是这个数是有重复的,原因是同一子树中的点对会在后面被重复计算,直接减去就好。

代码如下,注释很详细。

 

不如来评论一发?