本文主要是介绍POJ 1741 树的分治，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意就是求树上距离小于等于K的点对有多少个
n2的算法肯定不行，因为1W个点
这就需要分治。可以看09年漆子超的论文
本题用到的是关于点的分治。
一个重要的问题是，为了防止退化，所以每次都要找到树的重心然后分治下去，所谓重心，就是删掉此结点后，剩下的结点最多的树结点个数最小。
每次分治，我们首先算出重心，为了计算重心，需要进行两次dfs，第一次把以每个结点为根的子树大小求出来，第二次是从这些结点中找重心
找到重心后，需要统计所有结点到重心的距离，看其中有多少对小于等于K，这里采用的方法就是把所有的距离存在一个数组里，进行快速排序，这是nlogn的，然后用一个经典的相向搜索O(n)时间内解决。但是这些求出来满足小于等于K的里面只有那些路径经过重心的点对才是有效的，也就是说在同一颗子树上的肯定不算数的，所以对每颗子树，把子树内部的满足条件的点对减去。
最后的复杂度是n logn logn 其中每次快排是nlogn 而递归的深度为logn
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 11111
#define MAXM 55555
#define INF 1000000000
using namespace std;
struct EDGE
{这篇关于POJ 1741 树的分治的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
