大意

给定一棵树, 有点权, 求两两间点权互质的点的距离之和.

题解

数论

考虑使用容斥.

设 $p_1, p_2, \cdots , p_k$ 为 $1 \to \max(a_i)$ 中的质数.

设 $P_x$ 为树中两个点间点权的 gcd 为 $x$ 的倍数的路径集合, $d(P)$ 为 $P$ 的所有路径的长度之和.

那么

$$\text{res} = d(P_1) - d(P_{p_1} \cup P_{p_2} \cup \cdots \cup P_{p_k}) = d(P_1) - d(P_{p_i}) + d(P_{p_i} \cap P_{p_j}) + d(P_{p_i} \cap P_{p_j} \cap P_{p_l}) \cdots = d(P_1) - d(P_{p_i}) + d(P_{p_i p_j}) - d(P_{p_i p_j p_l}) \cdots (i \not= j \not= l)$$

观察上式的系数以及 $P_x$ 中的 $x$ 可以发现, $x = 1$ 时, 系数为 $1$, $x$ 有一个因数时, 系数为 $-1$, 两个为 $1$, 三个为 $-1$, 同时不存在 $x$ 有两个及以上因数的项.

可以发现符合莫比乌斯函数的性质.

所以

$$\text{res} = \sum_{i = 1}^{\max(a_j)} \mu(i) \cdot d(P_i)$$

树论

现在要求 $d(P_x)$.

可以用树上启发式合并.

设 $dis_x$ 为当前记录的子树中, $x \mid val_v$ 的 $\sum_u dep_v$.

那么, 点 $u$ 的贡献为:

$$\sum_{y \mid val_u} \mu(i) \cdot (dis_x + dep_{u} - 2 \cdot dep_{lca})$$

大意

给定若干物品, 一些物品可以直接购买, 不过有数量限制, 另一些物品需要若干其他的物品合成得到, 每个物品都有价值, 被合成消耗的物品不算价值, 给出购买的价钱限制, 求价值最大, 保证合成的方式构成森林.

题解

这题与其他的背包题不同的是, 需要分开来考虑用来用的和用来合成的, 需要加一个维度.

设 $f_{u, p, k}$ 为考虑到 $u$ 这个物品, $p$ 个用来合成, 花费 $k$ 的最大价值.
设 $q$ 为购买或者从下级合成而来的个数.

对于购买的物品:

$$f_{u, p, q \cdot cost_u} = val_u \cdot (q - p), \ p \le q \le lim_u$$

对于合成的物品:

$$f_{u, p, k} = max( (\sum_{v \in son(u), k = \sum k_v} f_{v, q \cdot cnt(v), k_v}) + val_u \cdot (q - p) , \ p \le q )$$

其中 $cnt(v)$ 表示合成 $u$ 需要 $cnt(v)$ 个物品 $v$.

合成的物品可以分别考虑需要的各个物品,
先枚举 $q$ , 再枚举 $v \in son(u)$.

$$g_{k} = \max_{0 \le k' \le k} g'_{k'} + f_{v, cnt(v)\cdot q, k - k'} \newline$$

$$f_{u, p, k} = \max\{f'_{u, p, k}, g_{k} + val_u \cdot (q - p)\} (p \le q) \newline$$

大意

给定一棵树, 树上预先有两个节点被标记, 每个单位时间, 被标记的点可以标记一个相连的点. 求把整课树标记的最小时间.

题解

考虑 dp.

设 $f_u$ 为将 $u$ 标记后, 还需多久将以 $u$ 为根的子树全部标记.

可以贪心处理: 设 $a$ 为 $f_v, v \in son(u)$ 从大到小排序后的结果,

那么 $f_u = a_1 + 1 + a_2 + 2 + ...$

然后将将树看作如下形式:

然后二分最初的点中间的链断开的位置, 分别从两侧转移, 求最大值.

断开的边越靠右, 左侧节点的 $f_{r1}$ 越大, 右侧的 $f_{r2}$ 越小.

而最优方案一定是 $|f_{r2} - f_{r1}|$ 最小, 故二分第一个使得 $f_{r1} > f_{r2}$ 的边即可.

大意

给定一个无向图, 有边权, 任意添加一条边, 使得任意删除一条边使得图不联通的代价最大.

题解

先跑一遍 Tarjan , 建出搜索树, 显然删除不是割边的边无法使图不联通, 故将它们的边权设为 $\infty$.

然后二分答案, 将边权比答案小的边的新边权设为 $1$ , 否则设为 $0$ (包括非割边) .

若要使答案成立, 必须找到一条路径, 使得覆盖所有的 $1$ 边.

如下图, 这显然不能成立:

这个可以成立:

显然, 选择直径最优. 然后跑一遍直径, 检查是否等于 $1$ 边的个数即可.

适用范围

树上的问题，对于一个节点，需要统计其的子树，且由于一些限制（主要是空间），无法直接合并多个直接子儿子的状态，只能 $\operatorname O (n^2)$ 统计，而 DSU on tree 可以优化至 $\operatorname O (n\cdot log n)$

做法

1. 树链剖分
2. 递归处理轻儿子，并删除贡献
3. 递归处理重儿子，并保留贡献
4. 计算轻儿子的贡献

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void dfs(int u, int f) // 树链剖分
{
    ...
}

void dsu(int u, int save /* 是否保留贡献 */)
{
    for (v <- edges(u))
        if (!heavy_son(v)) dsu(v, false);
    dsu(heavy_son(u), true);
    
    for (v <- all_son(u))
        if (v !in heavy_son(u)) add(v);
    
    res(u) = res(u) + calc()

    if (!save)
        for (v <- all_son(u))
            if (v !in heavy_son(u)) del(v);
}

适用范围

$$[l, r] \rightarrow_{\operatorname O(1)} [l, r+1], [l, r-1], [l+1, r], [l-1, r]$$

代码

1
2
3
4
5
6
7
8
9
10
11
12

sort(operations, (x, y) -> {
    key1 = left_block(x), left_block(y);
    key2 = right(x), right(y);
})

l = 1, r = 0;
for (o <- operations) {
    while (l < o.l) del(l++);
    while (l > o.l) add(--l);
    while (r < o.r) add(++r);
    while (r > o.r) del(r--);
}

复杂度

$$\operatorname O (n \sqrt n)$$

最极端的情况

每次 $r$ 右移一位，$l$ 在一个块中，至多移动 $\sqrt n$

大意

定义 $f(u, v)$ 为所有 $u$ 到 $v$ 的路径上, 路径上点权的最小值的最大的路径的最大值.

求 $\frac {\sum_{u, v, u \not= v} f(u, v)}{n(n - 1)}$ .

题解

倒序按照点权加入, 用并查集维护连通性.

每次对于新联通的连通块，如 $v$ , 对于该点的答案贡献 $val_u(size_v(size_u - size_v))$ ，其中，$u$ 为当前讨论的点.

(解释: 即里面选一个, 外面选一个)

最后, 再加上 $size_{old(u)}(size_u - size_{old(u)})$ . (解释: 当前点旧的连通块向新的连通块连边)

技巧

讨论最大值, 最小值时, 可以枚举最大值或最小值, 然后每次讨论时忽略更大或者更小的点.

大意

每次操作添加边或删除边或询问联通.

题解

线段树:

Node

merge

query

大意

给定一个无向图, 有若干询问，分两种.

1. 不经过某条边 $x \to y$，$a$ 是否能到达 $b$ ;
2. 不经过某个点 $x$，$a$ 是否能到达 $b$ ;

题解

先跑一遍 $Tarjan$ , 建出 $dfs$ 树.

设 $dep_x > dep_y$ .

询问一:

1. $x \to y$ 为非树边，可以到达;
2. $a, b$ 都在或都不在 $x$ 的子树中，可以到达;
3. $x \to y$ 并不是割边，可以到达;
4. 否则，无法到达;

询问二:

1. 若 $a$ 在 $x$ 的子树中，将 $a$ 向上跳至 $x$ 的直接儿子，此时 $x$ 必须不是割点;
2. $y$ 同理;
3. 假如跳完后 $a$ 和 $b$ 为同一点，可以到达;

大意

在有向图上, 有长度为 $x$ 的边, 对于每个询问，给定 $s, t$, 求出当 $x$ 取不同正整数时, 最短路的值有多少种, 并且求出他们的和.

题解

对原图跑分层图最短路, 记 $dis_{u, i}$ 为从 $s$ 至 $u$ , 恰好经过 $i$ 条长度为 $x$ 的边的最短路, 在求最短路时, 令 $x \leftarrow 0$.

可以得到若干条方程 $y_u = ix + dis_{t, i}$, 枚举考虑最短路经过 $i$ 条长度为 $x$ 的边的情况, 联立所有方程, 可以得到 (设 $f_i = dis_{u, i}$)

$$x \lt \frac {f_j - f_i} {i - j}, i > j \newline x \ge \frac {f_j - f_i} {i - j}, j < i \newline$$

然后可以求出 $x$ 的取值范围, 对答案的贡献即为

$$cnt \leftarrow cnt + hi_i - lo_i + 1 \newline$$

$$res \leftarrow res + i \frac {(hi_i + lo_i)(hi_i - lo_i +1)} 2 + dis_{t, i}(hi_i - lo_i + 1) \newline$$

(注: 不等式中, 不能两边都取等, 否则整数值会被重复考虑. )