点分治
树上点分治 其实就是把序列的分治方法移到了树上操作。序列上每个点的后继只有一个，树上可以有很多，我们找一个分支最多的出去，在不考虑常数的的情况下，这种分治方法是非常划算的。
静态分治
关于点分治的思想我不再赘述，很多博客已经讲得很清楚了。
我们实现上面代码，主要为下面几个函数。
寻找重心
在树上找重心的操作其实相当于在序列上找中点。1
int mid = (l + r) >> 1;
而我们在树上是这样操作的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17void getroot(int u, int f)
{
size[u] = 1;
mxs[u] = 0;
for (int it = head[u]; it != -1; it = edge[it].nxt)
{
int v = edge[it].v;
if (vis[v] || v == f)
continue;
getroot(v, u);
size[u] += size[v];
mxs[u] = max(mxs[u], size[v]);
}
mxs[u] = max(mxs[u], tsize - size[u]);
if (mxs[u] < mxs[root])
root = u;
}
（其实就是树上跑个dp）
分治
得到重心之后，我们分治重心的每个分支，最后相当于pushup上来。
注意在这个函数里要进行一些找重心的初始化。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void solve(int u, int f)
{
vis[u] = 1;
ans += get(u, 0); //治
for (int it = head[u]; it != -1; it = edge[it].nxt) //分
{
int v = edge[it].v;
if (v == f || vis[v])
continue;
ans -= get(v, edge[it].d); //治
root = 0;
tsize = size[v];
getroot(v, 0);
solve(root, u);
}
}
计算每个分支的答案
这一部分就是我们随意发挥的地方了，我们可以在这里进行一些复杂度约为O(n)计算，达到和序列分治类似甚至更优的效果。
POJ1741
以此题为例，我们来搞一波树上点分治。
在大部分博客中，分治部分代码对小子树大小的计算方法我觉得有问题，于是后来自己在原来我的AC代码上做了一番修改，貌似还是有几十毫秒的改进的。
虽然原来方法复杂度也不是很高，但是在那样的基础上计算会影响我们对树上动态点分治的理解，因为那样每次不一定找到的是重心。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
using namespace std;
typedef long long ll;
const int N = 1e4 + 5;
struct node
{
int v, nxt, d;
}edge[2 * N];
int head[N], tot;
int size[N], root, mxs[N], vis[N], tsize;
int cnt[N], k;
void init(int n)
{
for (int i = 1; i <= n; i++)
head[i] = -1, vis[i] = 0;
root = 0;
tot = 0;
tsize = n;
mxs[0] = 0x3f3f3f3f;
}
void addedge(int u, int v, int d)
{
edge[++tot].v = v;
edge[tot].nxt = head[u];
edge[tot].d = d;
head[u] = tot;
}
void getroot(int u, int f)
{
size[u] = 1;
mxs[u] = 0;
for (int it = head[u]; it != -1; it = edge[it].nxt)
{
int v = edge[it].v;
if (vis[v] || v == f)
continue;
getroot(v, u);
size[u] += size[v];
mxs[u] = max(mxs[u], size[v]);
}
mxs[u] = max(mxs[u], tsize - size[u]);
if (mxs[u] < mxs[root])
root = u;
}
int cur = 0;
ll ans = 0;
void calc(int u, int f, int d)
{
cnt[++cur] = d;
size[u] = 1;
for (int it = head[u]; it != -1; it = edge[it].nxt)
{
int v = edge[it].v;
if (v == f || vis[v])
continue;
calc(v, u, d + edge[it].d);
size[u] += size[v];
}
}
int get(int u, int d)
{
cur = 0;
calc(u, 0, d);
sort(cnt + 1, cnt + cur + 1);
int head = 1, tail = cur;
int ret = 0;
while (head < tail)
{
if (cnt[head] + cnt[tail] <= k)
{
ret += tail - head;
head++;
}
else
tail--;
}
return ret;
}
void solve(int u, int f)
{
// dbg(u);
vis[u] = 1;
ans += get(u, 0);
for (int it = head[u]; it != -1; it = edge[it].nxt)
{
int v = edge[it].v;
if (v == f || vis[v])
continue;
ans -= get(v, edge[it].d);
root = 0;
tsize = size[v];
// puts("getroot");
// dbg(v, tsize);
getroot(v, 0);
solve(root, u);
}
}
template<class T>
void read(T& ret)
{
ret = 0;
char c;
while ((c = getchar()) > '9' || c < '0');
while (c >= '0' && c <= '9')
{
ret = ret * 10 + c - '0';
c = getchar();
}
}
int main()
{
int n;
while (true)
{
read(n);
read(k);
if (n == 0 && k == 0)
break;
init(n);
for (int i = 1; i < n; i++)
{
int u, v, d;
read(u);
read(v);
read(d);
addedge(u, v, d);
addedge(v, u, d);
}
ans = 0;
root = 0;
getroot(1, 0);
solve(root, 0);
printf("%lld\n", ans);
}
return 0;
}
动态点分治
有了前面的基础，我们来了解一下动态点分治。
动态在哪里
我们之所以将这种点分治和之前加以区分，是因为这一类题目会要求可以做一些修改，而显而易见我们不能每次暴力修改然后查询的时候用O(nlog(n))时间去查询，这是十分爆炸的。
解决方案
还是考虑分治的时候，如果我们要求修改某一个点，那么我们可以像线段树那样每次取一半，看看要修改的点在哪个区间，然后向上层push。
我们这样只去修改会受到影响的log(n)级别个区间，查询类似。
为了方便快捷地知道我们后面该往哪里走，先预处理出一棵点分树，在这棵树上是我们寻找重心的顺序，后面将会用到这棵树。
点分树
这棵树是由我们原本的树建出来的，但是树形又和原来不同。
点分树的父子关系，是由原树的分治顺序决定的，也就是说，我们寻找重心的时候的顺序，其实应该是点分树上的遍历顺序。既然这样，那我们的数其实也是比较好建立了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16inline void get_tree(int u, int f)
{
//dbg(u);
vis[u] = 1;
fa[u] = f;
for (int it = head[u]; it != -1; it = edge[it].nxt)
{
int v = edge[it].v;
if (vis[v])
continue;
root = 0;
tsz = size[v];
get_root(v, u, 1);
get_tree(root, u);
}
}
使用点分树
我们要这样一棵树有什么用呢？其实理解树上点分治的话，就会觉得这棵树其实是很有必要的。我们要维护这棵树上的一些父子关系。
分治的过程，我们要知道当前这一部分要往哪个点合并，知道方向我们才好处理。为了不用每次都去get_root，我们预先把所有点父子关系存下来。
就像我们在归并的时候向上返回，总要做些处理，如果当前区间已经覆盖了要修改或查询的点，直接返回，否则分半去修改或查询。
使用方法需要随机应变的。
BZOJ3730 震波
1 |
|