RenaMoe's Blog

念念不忘，必有回响

0%

总结 点分治

发表于 更新于 分类于 ， Valine：

用于某些统计树上路径的题

每次找树的重心为根（\(O(n)\)）

处理每个点到根的距离等信息（\(O(n)\)）

统计答案（\(O(n)\)或\(O(nlogn)\)等）

划分根的各个子树，分治下去（总共分治\(logn\)层）

模板部分

getroot() 找树的重心

1
2
3
4
5
6
7
8
9
10
11
12
13
void getroot(int u, int fa, int size) {
    sz[u] = 1, maxs[u] = 0;
    for (int i = head[u], v; i; i = e[i].nxt) 
        if (!vis[e[i].to] && e[i].to != fa) {
            v = e[i].to;
            getroot(v, u, size);
            sz[u] += sz[v];
            maxs[u] = max(maxs[u], sz[v]);
        }
    maxs[u] = max(maxs[u], size - sz[u]);
    if (!root || maxs[u] < maxs[root])
        root = u;
}

getdis() 处理各点的距离

1
2
3
4
5
6
7
8
// 带染色
void getdis(int u, int fa, int dis, int color) {
    t[++tot] = u;
    d[u] = dis, col[u] = color;
    for (int i = head[u], v; i; i = e[i].nxt)
        if (e[i].to != fa && !vis[e[i].to])
            v = e[i].to, getdis(v, u, d[u] + e[i].val, color);
}

统计答案时会重复，同一子树中的两个点是不能成点对的

有两种方式，将各个子树染色，或是通过容斥原理减去子树的一部分答案

solve() 分治

1
2
3
4
5
6
7
8
9
10
11
void solve(int u) {
    vis[u] = true;
    ans += calc(u, 0);
    for (int i = head[u], v; i; i = e[i].nxt) 
        if (!vis[e[i].to]) {
            v = e[i].to, root = 0;
            ans -= calc(v, e[i].val);// 染色的话不加这句话
            getroot(v, 0, sz[v]);
            solve(root);
        }
}

统计答案

calc() 每道题是不同的

以模板题为例

1
给定一棵有n个点的树，询问树上距离为k的点对是否存在

将每个点的深度处理出来后，按深度排序

1
2
3
4
5
6
7
tot = 0;
t[++tot] = u;
d[u] = dis, col[u] = u;
for (int i = head[u], v; i; i = e[i].nxt)
    if (!vis[e[i].to])
        v = e[i].to, getdis(v, u, d[u]+e[i].val, v);
sort(t+1, t+tot+1, cmp);

此时又有两种方法：

  • 双指针扫
1
2
3
4
5
6
7
8
9
10
11
12
13
int l = 1, r = tot;
while (l < r) {
    if (d[t[l]] + d[t[r]] > k)
        r--;
    else if (d[t[l]] + d[t[r]] < k)
        l++;
    else if (col[t[l]] == col[t[r]])
        d[t[r]] == d[t[r-1]] ? r-- : l++;
    else {
        ans = true;
        break;
    }
}
  • 二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int l = 1, r;
while (l < tot && d[t[l]] + d[t[tot]] < k)
    l++;
while (l < tot) {
    if (d[t[l]] > k - d[t[l]])
        break;
    d[0] = k - d[t[l]];
    r = lower_bound(t+1, t+tot+1, 0, cmp) - t;
    while (r <= tot && d[t[l]] + d[t[r]] == k) {
        if (col[t[l]] != col[t[r]])
            ans = true;
        r++;
    }
    l++;
}

复杂度上限在于排序（\(O(nlogn)\)）

如果可以的话，可以桶排，降到（\(O(n)\)）

一些题目

P4178树上长度小于等于k的路径

P4149长度为k的路径最小边数

我菜，好多还没做过。。。