树上点分治

这几天一直想完成之前的点分治,但都在写其他题,今天终于写完了点分治,怕忘,就写一下博客。

【引言】

由于树具有一般的图没有的特点,所以在竞赛中的应用更广。

在一些树上路径问题中,暴力求解时间复杂度过高,往往需要一些更为高效的算法,点分治就是其中之一。

【思想】

在树上,取一个点,对于询问计算所有经过这个点的情况,再递归下去处理每一棵子树的情况。因为是递归处理,为了使递归的次数更少,一般都是要取使以其为根,所有子树中节点最多的子树拥有的节点最少,称这个点为“重心”。

重心求法如下:

(1)任取一个根,dfs一次求出每个节点的子树大小。

(2)记录每一个点最大子树的节点数。

(3)最大子树的节点最少的点便是重心

代码如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
[cce_cpp]
void Getroot(int x, int fa)  {
    son[x] = 1;
    Max[x] = 0;
    int next;
    for (int i = last[x]; i ;i = e[i].last)
        if (!use[next = e[i].t] && next != fa)  {
            Getroot(next, x);
            son[x] += son[next];
            Max[x] = max(Max[x], son[next]);
        }
    Max[x] = max(Max[x], Son - son[x]);//因为这个点不一定是根,要计算它上的节点数,用树的大小减去(它的子节点数+1)即可
    if (Max[x] < Max[root]) root = x;
}
[/cce_cpp]

时间复杂度O(n)。

求出重心接下来就要解决问题了
(1)关于询问,以重心为根,求出所有经过当前重心的情况(即子节点1-->重心-->子节点2)。因为为了节省时间,是把所有子节点的情况一起算,如果两个子节点来自同一棵子树,那肯定是不行的,所以还要减去所以来自同一棵子树的子节点的情况。
(2)标记重心
(3)递归用相同的方法处理每一棵子树。
代码如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
void sol(int x)  {
    root = 0;
    Getroot(x, 0);
    use[root] = 1;
    ans += Cal(root, 0);
    int next;
    for (int i = last[root]; i ;i = e[i].last)
        if (!use[next = e[i].t])  {
            ans -= Cal(next, e[i].val);
            Son = son[next];
            sol(next);
        }
}

点分治的思想基本上如上所述。

【例题】

继续阅读树上点分治