qzc大神的那篇论文很早就看了,当时没有理解,这个坑就一直在那了。
最近又想起来去看看,突然好像有点懂了,然而现在只会裸题。

如果我们有一个和路径相关的问题,那么可以想想是不是能用点分治处理。

递归分治

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int x) {
ans += solve(x, 0);
vis[x] = 1;
for (int i = head[x]; ~i; i = e[i].next) {
int v = e[i].to, w = e[i].val;
if (vis[v]) continue;
ans -= solve(v, w);
sum = sz[v]; root = 0;
get_root(v, 0);
dfs(root);
}
}

这样子做要让复杂度是对的,那么每次就要找到树的重心作为根。

重心

对于有$N$个结点的树来说,就是每次去找一个根,这个根的性质是:把它删掉之后,最大的树大小不超过$N/2$。
有个结论是必然可以找到一个点,满足上面的性质。
我们可以反证一下:
假找不到这个点,也就是说存在一个点$v$的$sz[v]>n/2$
那么我们把这个点拎成根,可以发现以其子结点为根的子树都不超过$N/2$
这样每次规模都减半,复杂度就对了。

1
2
3
4
5
6
7
8
9
10
11
12
void get_root(int x, int par) {
sz[x] = 1; f[x] = 0;
for (int i = head[x]; ~i; i = e[i].next) {
int v = e[i].to;
if (v == par || vis[v]) continue;
get_root(v, x);
sz[x] += sz[v];
f[x] = max(f[x], sz[v]);
}
f[x] = max(f[x], sum - sz[x]);
if (f[x] < f[root]) root = x;
}

poj1741

题意是说,求树上路径长度<=k的路径条数。
点分治模板题,统计经过根的满足条件的路径数,统计的时候要减去那些不合法的贡献,然后递归分治下去。
不合法的贡献其实就是那些从同一棵子树上来的路径,那么把这些减掉就好了。

这里有一个子问题:有一些数,求两个数和<=k的对数。
先排序,然后两个指针,p从大到小,q从小到大;
这样子保证了q只走一遍$O(n)$,复杂度是$O(n+n)$线性的。

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
void get_dist(int x, int par) {
dist[++dist[0]] = d[x];
for (int i = head[x]; ~i; i = e[i].next) {
int v = e[i].to, w = e[i].val;
if (v == par || vis[v]) continue;
d[v] = d[x] + w;
get_dist(v, x);
}
}
int solve(int x, int w) {
d[x] = w; dist[0] = 0;
get_dist(x, 0);
sort(dist + 1, dist + 1 + dist[0]);
int ret = 0;
int j = 0;
for (int i = dist[0]; i >= 1; --i) {
if (j >= i) {
ret += i - 1;
continue;
}
while (j + 1 <= dist[0] && dist[i] + dist[j + 1] <= k) ++j;
if (j >= i) ret += i - 1;
else ret += j;
}
return ret;
}

bzoj2152

和上面的例题类似,只是把条件换成了被3整除。

bzoj1095

未完待续。。。