Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

01/8
19:39
图论 点分治

BZOJ 1468 tree 点分治

Description

给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

Input

N(n<=40000) 接下来n-1行边描述管道,按照题目中写的输入 接下来是k

Output

一行,有多少对点之间的距离小于等于k

Sample Input

7

1 6 13

6 3 9

3 5 7

4 1 3

2 4 20

4 7 2

10

Sample Output

5

HINT

Source

LTC男人八题系列

 

 

话说最近做了好几个叫tree的题…… 点分治……楼教主男人八题系列,好可怕QAQ

点分治,就是基于点的树的分治啊。首先要找到一个根(树的重心),然后呢把所有的路径分为两种:经过根的和不经过根的,经过根的直接计算,不经过的递归计算。这样会把子树内不必要的路径也计算上,所以再删去这一部分。

 

最后再附一篇看过的论文吧……

分治算法在树的路径问题中的应用