DDOSvoid's Blog

点分治

发表于 更新于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

简介

点分治一般是用来处理树上路径问题

一般的思想是对于每条路径 $u\rightarrow v$，我们在 $lca(u,v)$ 处统计它们的贡献

对于一棵树，我们选择它的重心为根，然后统计每个点到根的权值和

这样就得到了所有以根为 $lca$ 的贡献

对于每个子树内的点对的贡献，我们递归进行处理

时间复杂度为 $O(log*\alpha)$，其中 $\alpha$ 为每层处理的时间复杂度

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
bool vis[maxn];
namespace DF {
    int f[maxn], sz[maxn];
    int sum, rt, maxdp;

    inline void init(int n) { f[rt = 0] = n + 1; fill(vis + 1, vis + n + 1, false); }
    void dfs_sz(int u, int fa) {
        sz[u] = 1; 
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to; if (v == fa || vis[v]) continue;
            dfs_sz(v, u); sz[u] += sz[v]; 
        }
    }
    void dfs(int u, int fa) {
        f[u] = 0;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to; if (v == fa || vis[v]) continue;
            dfs(v, u); f[u] = max(f[u], sz[v]); 
        } f[u] = max(f[u], sum - sz[u]);
        if (f[u] < f[rt]) rt = u; 
    }
    inline int get_rt(int u) {
        rt = 0; dfs_sz(u, 0);
        sum = sz[u]; dfs(u, 0); return rt; 
    }
};

例题

  1. 简要题意：给定一棵 $n$ 个点的无根树，每个点有一个物品，物品有重量 $w$，价值 $c$ 和数量 $d$ 这三个属性，现在要在树上做多重背包，给定重量 $m$，你现在可以选择的物品必须满足在一个连通块内，即如果你选了 $u$ 和 $v$ 中至少一个物品，那么 $u$ 和 $v$ 路径上的每个点你都必须至少选一次

    $n\le 500,m\le 4000,w\le m,d\le 100$

    简要题解：我们注意到合并两个背包的复杂度为 $O(m^2)$，而插入一个物品的复杂度为 $O(m)$，我们考虑求必须包含根节点的答案，然后按照点分的过程，求不包含当前根节点的答案

    我们以 $dfs$ 序的逆序来背包，因为一个点的子树的 $dfs$ 序是一个段区间，我们当前考虑点 $i$，那么我们有两种抉择，不选 $i$，那么 $i$ 的子树也无法选择，那么 $f_i$ 就等于 $f_{i+sz_i}$；强制选择 $i$ 的一个物品，那么 $i$ 的子树可以随便选，那么 $f_i$ 就等于 $f_{i+1}$ 插入 $(w_i,c_i,d_i)$ 这个物品，注意需要保证这个物品至少选 $1$ 个，容易发现这两种情况合并只需要对应位置取 $max$ 即可

    时间复杂度 $O(nm\log n)$，如果使用二进制拆分优化多重背包，那么时间复杂度为 $O(nm\log n\log d)$

    树上依赖性背包

    Luogu P6326 Shopping