点分治专题——bzoj 1468 &bzoj 2152 题解

【前言】最近一直在忙着学算法，但是效果似乎不是很好。前段时间的树剖也快忘了= =。树套树没熟练，就开始写主席树了= =。更别说本身就不是很懂的莫比乌斯反演了。~~决定好好复习一下。

【点分治的作用】套用SYC大神的话说是：用来解决树上路径点权统计问题。

【大致流程】

①找出这颗树的重心。

②统计经过这个重心的答案

③用重心把树割开

④对每个“小树”做同样的事

【Q1——重心】其实找重心再进行计算只是为了不被卡链。什么是重心?就是当前树中的一个点K，使得MAX(SON[K])最小。SON[K]指的是以K为根的情况下某个孩子的点数。感性的想，重心在树的中间位置。

【Q2——统计答案】假设我们已经确定了一个重心K。我们先计算和K有关的（即经过K的路径或是以K为起点/终点的路径）答案个数，然后再递归每一棵小树，同样进行找重心、计算的过程。而且有些时候，我们计算出有关K的答案是有重复的，因此我们在递归的时候还要减去重复的（容斥原理）。

【Q3——边界】怎么使得某棵小树和其他树分开呢？其实很简单，我们可以开个1..n的布尔数组，表示x是否成为过重心。如果成为过，我在搜索的时候就可以直接退出了。

【T1——BZOJ】

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 306  Solved: 139

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

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

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

7

1 6 13

6 3 9

3 5 7

4 1 3

2 4 20

4 7 2

10

5

【分析】真是一道经典题，POJ,USACO上都有。我们每次找到重心K后，把每个点到K的相对距离都算出来。然后把他们存到一个数组里去，用O(NLOGN)的快排和O(N)的扫描算出点对数。但是这样是有重复的，如图。

这样的话，设K=1，那么3和4这一条（假设3-2-1-2-4是符合要求的）就重复算了。于是我们在2--3--4这棵树中，把3-2-4这条路给删掉。怎么实现呢？我们调用左下角的小树，给d[3]一个初始值path[1][2]。这样我们可以得到d[3]=path[1][2]+path[2][3],d[4]=path[1][2]+path[2][4]。如果3-2-1-2-4符合要求，这当然也符合。这样就可以成功地删掉了。

【代码】

【T2——BZOJ2152】

Time Limit: 3 Sec  Memory Limit: 259 MB

Submit: 335  Solved: 178

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

输入的第1行包含1个正整数n。后面n-1行，每行3个整数x、y、w，表示x号点和y号点之间有一条边，上面的数是w。

以即约分数形式输出这个概率（即“a/b”的形式，其中a和b必须互质。如果概率为1，输出“1/1”）。

1 2 1

1 3 2

1 4 1

2 5 3

13/25

【样例说明】

13组点对分别是(1,1) (2,2) (2,3) (2,5) (3,2) (3,3) (3,4) (3,5) (4,3) (4,4) (5,2) (5,3) (5,5)。

【数据规模】

对于100%的数据，n<=20000。

【分析】可能这道更简单吧，不用快排，也不用去重。我们对于当前的树G，若找到的重心是K，我们就从K出发，搜索与K相邻的点，寻找边长的余数分别是是0,1,2的情况数，然后分情况讨论。