积性函数，莫比乌斯反演（一）

[[ slider_text ]]

[[ item.c ]]

积性函数，莫比乌斯反演（一）

发布时间 2024-11-28 作者：zhangminchen 来源：算法小站

树形dp 欧拉函数 线性筛 积性函数

## 积性函数
### 积性函数的定义
定义在正整数上的，对**任意一对互质**的正整数对$$(p, q)$$，均有$$f(pq) = f(p)f(q)$$
称$$f$$是积性函数

几个例子
$$1(n) = 1$$
$$id(n) = n$$
$$\epsilon(n) = [n = 1]$$
$$\phi(n) = 1\cdots n \text{ 中和 n 互质的数的数量}$$
$$d(n) = \text{n 的正因子的数量}$$

简单证明一下$$d(n)$$的积性
不妨设$$n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$$，那么其因子有形式$$p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k}$$
其中$$0 \leqslant \beta_i \leqslant \alpha_i$$，那么问题转化成对每个$$\beta_i$$
有几种可能的取值？
把所有答案乘起来，正因子的数量为$$(\alpha_1 + 1)(\alpha_2 +2 )\cdots (\alpha_k +k)$$
如果$$(p, q)$$互质，那么很显然$$(p, q)$$是独立的，都可以单独计算
然后乘起来，这是满足积性的

### 积性函数的性质
如果$$f(n), g(n)$$是积性函数，那么$$f(n)g(n)$$也是积性函数

**快速计算积性函数**
设$$f$$是积性函数，不妨设$$n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$$
那么$$f(n) = f(p_1^{\alpha_1}) f(p_2^{\alpha_2})\cdots f(p_k^{\alpha_k})$$

```bash
ll getf(ll n) {
    ll ans = 1;
    for (int i = 2; i <= n/i; i++) {
        int cnt = 0;
        while (n % i == 0) cnt++, n /= i;
        // f(p, k) = f(p^k)
        ans *= f(i, cnt);
    }
    if (n > 1) ans *= f(n, 1);
    return ans;
}
```

### 简单积性函数的计算，欧拉函数

**欧拉函数**
因为欧拉函数的定义，$$\phi(n)$$表示$$[1, n]$$中和$$n$$互质的元素的个数

不妨设$$n = pq$$，那么我们要从$$n$$个数中扣除$$p$$和$$q$$倍数的个数
注意到$$p$$的倍数有$$p, 2p, \cdots, \lfloor \dfrac{n}{p}  \rfloor \cdot p$$，$$\lfloor \dfrac{n}{p}\rfloor $$个
而$$q$$的倍数有$$\lfloor \dfrac{n}{q} \rfloor$$个
同时，$$(pq)$$的倍数有$$\lfloor \dfrac{n}{pq} \rfloor$$个，这部分在容斥中，被重复计算了

所以答案是$$n - \dfrac{n}{p} - \dfrac{n}{q} + \dfrac{n}{pq} = n(1-\dfrac{1}{p})(1-\dfrac{1}{q})$$

那么对于多因子的情况，就是
```math
\displaystyle
n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2}) \cdots (1-\dfrac{1}{p_k}) \\
= p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} (\dfrac{p_1-1}{p_1})\cdots (\dfrac{p_k-1}{p_k}) \\
= (p_1-1)p_1^{\alpha_1 - 1}\cdot (p_2 - 1)p_2^{\alpha_2 - 1} \cdots (p_k - 1)p_k^{\alpha_k - 1}
```

根据以上表达式，只需要在质因子分解的基础上，稍微修改即可
```bash
ll phi(ll n) {
    ll res = 1;
    for (int i = 2; i <= n/i; i++) {
        if (n % i == 0) {
            res *= (i-1);
            n /= i;
            while (n % i == 0) res *= i, n /= i;
        }
    }
    if (n > 1) res *= (n - 1);
    return res;
}
```
如果需要打表，求出$$\phi(1), \phi(2), \cdots, \phi(n)$$怎么办？，注意到
```math
\displaystyle
\phi(n) = n \cdot \prod_{i = 1}^{k} \left( \dfrac{p_i-1}{p_i} \right)
```
而对于质数而言，$$\phi(p) = p-1$$
在**Eratosthenes 筛**中，用**素数来筛掉合数（它的倍数）**，可以对 Eratosthenes 筛稍微加以修改

1）初始化$$\phi(i) = i$$，对**所有的**$$i \in [2, n]$$
2）注意到如果一个数是合数，它被筛出来之后，一定有$$\phi(i) \neq i$$，因为我们从小到大遍历去筛所有的合数
也就是说，一个合数一定会被它的素因子给筛过
如果遍历时候有$$\phi(i) = i$$，那么说明$$i$$是素数，枚举$$i$$所有的倍数$$j$$
每一个$$j$$，令$$\phi(j) = \phi(j) \cdot (i - 1) / i$$即可
```bash
void solve() {
    // composite number, we have phi(i) != i
    vector<int> phi(maxn, 0);
    
    auto phiTable = [&]() -> void {
        iota(phi.begin()+2, phi.end(), 2);
        for (int i = 2; i <= n; i++) {
            if (phi[i] == i) {
                for (int j = i; j <= n; j += i) {
                    phi[j] = phi[j] / i * (i - 1);
                }
            }
        }
    };

phiTable();
}
```

### 线性筛求积性函数
#### 线性筛回顾
要求每个合数，只会被它的**最小素因子筛掉**

1）维护已经遍历过的素数数组$$P,  p \in P$$
2）在`for i`的时候，如果`i`没有被筛过，那么$$i \to P$$，把`i`放入素数集合中
（Eratosthenes 筛只需要标记合数，而欧拉 seive 除了标记合数之外，需要额外维护已经遍历过的素数集合）
标记$$p \cdot i$$为合数
如果$$i \bmod p = 0$$，说明$$i$$已经被$$p$$筛过了，break

**证明如下**
考虑$$x = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$，其中$$p_1 < p_2 < \cdots p_k$$
因为$$p_1 < p_2$$，所以呢？$$p_1^{\alpha_1 - 1}$$之后的合数，一定是$$p_1^{\alpha_1}$$
而不会是$$p_1^{\alpha_1 - 1} \cdot p_2$$，因为$$p_1^{\alpha_1} < p_1^{\alpha_1 -1} \cdot p_2$$

对素因子归纳，不难发现，遍历的时候，我们一定是按如下顺序考虑
$$p_1^{\alpha_1} \to p_1^{\alpha_1} p_2 \to p_1^{\alpha_1} p_2^{\alpha_2} \to \cdots $$
（考虑完$$p_1$$所有的幂指之后，才轮到$$p_2$$）
当考虑素因子$$p_2$$的时候，包含$$p_2$$的最小的数，一定是$$p_1^{\alpha_1} \cdot p_2$$，而$$p_1 \mid p_1^{\alpha_1}p_2$$
它已经被$$p_1$$筛过了，直接 break 即可

#### 线性筛模版题
**[Sum of Consecutive Prime Numbers](https://ac.nowcoder.com/acm/contest/21094/B)**
求$$n$$能表示成连续质数之和的方案数

**算法分析**
打表$$[1, n]$$所有的素数，然后求一遍前缀和$$S$$
```bash
把所有的 S 放入哈希表中，也包括 S[0] = 0
for 所有的 S[j]，看一下 n - S[j] 是否在哈希表中，是的话，ans += 1

// 滑窗算法如下
维护滑动窗口数的和 sum，let sum = 0
for i = all primes
	j = max(j, i)
	while (j < primes.size()  and sum < n) sum += primes[j], j += 1
	if (sum == n) ans += 1;
	sum -= primes[i]
```
当然，如果数据范围给的很大，用哈希表`map`，可能会超时，把算法改成**滑动窗口**即可
（因为`primes`中连续的一段数，滑动窗口越大，`sum`就越大，前缀和是单调递增的）

**[Prime Distance](https://ac.nowcoder.com/acm/contest/21094/C)**
给定一个区间$$[L, R]$$，求距离最近的一对素数和最远的一对素数，如果距离相同，输出最小的一对

**算法分析**
实际上不需要筛$$1 \sim R$$中所有的素数，只筛$$[L, R]$$中的素数，这又称为**区间筛**
筛法实际上是用**素数去标记它的倍数**，不妨设合数$$x = i \cdot j, i < j$$
那么只要让$$x$$被较小的那个数$$i$$给筛掉即可，$$j$$是没有用的，也就是说对于$$[1, x]$$的素数
我们只需要考虑$$[1, i^2]$$即可，更大的数没有用，对于区间$$[1, R]$$，实际上只需要枚举$$[1, \sqrt{R}]$$即可

1）对$$[1, \sqrt{R}]$$中的所有素数打表，令$$p \in Pri$$
2）用$$p$$去标记$$[L, R]$$区间中$$p$$**的倍数**
都做完了之后，扫描一下区间，除去这些标记的合数，就是区间内所有素数

> 那么怎么标记区间$$[L, R]$$中，最接近$$L$$的，$$p$$的倍数

实际上，我们需要$$(? \cdot p) \geqslant L$$，也就是$$? \geqslant \lceil \dfrac{L}{p} \rceil$$

区间$$[L, R]$$最小的，$$p$$的倍数是$$p \cdot \dfrac{L+p-1}{p}$$

#### 线性筛求欧拉函数
**前置定理**
> 如果$$m$$是一个素数幂$$p^k$$，那么$$\phi(p^k) = p^k - p^{k-1}$$

证明并不难，$$< p^k$$，并且$$gcd(?, p^k) \neq 1$$的数有$$\\{0, p, 2p, \cdots, p^k - p\\}$$
这里一共有$$p^{k-1}$$个数，所以$$\phi(p^k) = p^k - p^{k-1}$$

> 只需要对欧拉筛稍做修改即可

欧拉筛的关键就在于，$$i$$被$$p$$筛出来的时候，考虑$$i \bmod p = 0 \text{ or } \neq 0$$
1）如果$$i \bmod p \neq 0$$，说明$$(i, p) = 1$$（它们互素）
此时有$$\phi(i \cdot p) = \phi(i) \cdot \phi(p) = \phi(i) \cdot (p-1)$$

2）如果$$i \bmod p = 0$$，那么说明$$i$$中已经有**至少 1 个**素因子$$p$$了，可以发现
$$\phi(i) = \phi(j) \cdot \phi(p^k) = \phi(j) \cdot (p^k - p^{k-1})$$
$$\phi(i \cdot p) = \phi(j) \cdot \phi(p^{k+1}) = \phi(j) \cdot (p^{k+1} - p^k) = \phi(i) \cdot p$$

那么欧拉筛求欧拉函数的算法可以描述如下
1）如果`!notprime(i)`，那么$$i$$是素数，$$\phi(i) = i-1$$
2）考虑已经遍历过的所有素数$$p$$，如果$$i \bmod p = 0$$
说明$$i$$已经有一个素因子$$p$$了，已经被筛过一遍了，之前筛的时候$$\phi(i^{\prime})$$已经求出来了
在 break 之前，记$$\phi(i \cdot p) = \phi(i) \cdot p$$
3）其他情况，就是$$(i, p) = 1$$，那么$$p$$就是$$i \cdot p$$的最小素因子
记$$\phi(i \cdot p) = \phi(i) \cdot (p-1)$$

#### 线性筛求一般积性函数
不妨设我们要求积性函数为$$f(x)$$
和求欧拉函数类似，$$calc(p, k)$$表示求$$f(p^k)$$
在欧拉筛的时候，$$p$$能筛掉$$(i \cdot p)$$，当且仅当$$p$$是$$(i \cdot p)$$的**最小素因子**
我们还需要一个$$cnt(x)$$（方便求出`cnt[ i*p ]`），表示$$x$$中**最小素因子的次数**

也是类似的分类讨论
1）如果$$i \bmod p = 0$$，说明$$i$$之前已经有一个素因子$$p$$了，之前$$i$$中素因子$$p$$的次数是$$cnt_i$$
那么在$$i \cdot p$$中，$$p$$的次数是$$cnt(i \cdot p) = cnt(i) + 1$$
至于积性函数中的$$f(p^k)$$，变化成$$\to f(p^{k+1})$$
2）否则的话，$$(i, p) = 1$$，$$(i \cdot p)$$中最小素因子就是$$p$$，且它的次数为$$1$$
那么$$cnt(i \cdot p) = 1$$，此外$$f(i \cdot p) = f(i) \cdot f(p) = f(i) \cdot calc(p, 1)$$

```bash
void solve() {
    vector<int> f(maxn, 0);
    f[1] = 1;

auto calc = [&](int p, int k) -> int {
        // calc p^k
    };

vector<int> primes;
    auto mulfun = [&]() -> void {
        vector<int> notprime(maxn, 0);
        vector<int> cnt(maxn, 0);

for (int i = 2; i < maxn; i++) {
            if (!notprime[i]) primes.push_back(i), f[i] = calc(i, 1);
            for (auto p : primes) {
                if (i * p >= maxn) break;
                notprime[i * p] = 1;
                if (i % p == 0) {
                    cnt[i * p] = cnt[i] + 1;
                    f[i * p] = f[i] / calc(p, cnt[i]) * calc(p, cnt[i]+1);
                    break;
                }
                cnt[i * p] = 1;
                f[i * p] = f[i] * calc(p, 1);
            }
        }
    };
}
```

## 一些很杂的问题
### 阶乘分解
分解$$n!$$，分解成素因子相乘的形式

直接做复杂度太高，实际上，我们**一个一个素因子考虑**
对于某一个素因子$$p$$，需要考虑它会在$$n!$$出现几次？实际上等价于$$1\sim n$$中有几个$$p$$

首先对$$n$$进行素因子分解，对于某个素因子$$p$$
考虑$$p$$的倍数，$$p, 2p, 3p, \cdots,p\cdot p, \cdots \lfloor\dfrac{n}{p} \rfloor\cdot p$$，共$$\lfloor\dfrac{n}{p} \rfloor$$个
考虑$$p^2$$的倍数，$$p^2, 2p^2, \cdots, p \cdot p^2, \cdots, \lfloor \dfrac{n}{p^2} \rfloor \cdot p^2$$，共$$\lfloor \dfrac{n}{p^2} \rfloor$$ 个

好了，问题来了，第一个$$p\cdot p$$，和第二个$$p^2$$是否会重复统计？
实际上不会，因为在第一次统计的时候，虽然是$$p\cdot p$$，但我们只统计一次，而不是两次
我们统计的是**第一个最低数位上的$$p$$**
那到了第二次考虑$$p^2$$作为因子的时候，我们只统计**第二个数位上的$$p$$**
换句话说，上述过程执行下来，**每个数位上出现的$$p$$都只会被统计一次**，不会重复
所以答案是$$\lfloor \dfrac{n}{p} \rfloor + \lfloor \dfrac{n}{p^2} \rfloor + \lfloor \dfrac{n}{p^3} \rfloor +\cdots + \lfloor \dfrac{n}{p^k} \rfloor $$

## Codeforces Round 922 (Div. 2)
**[C. XOR-distance](https://codeforces.com/contest/1918/problem/C)**
**问题描述**
最小化 $$|(a \oplus x) - (b \oplus x)|$$，其中要求$$0 \leqslant x \leqslant r$$
### 算法分析
想倒是不难想，首先不管$$x$$取什么数，一位一位来看，对于低位来说
如果$$a_i = b_i$$，不管是$$0, 1$$，答案是没有影响的
那么关键就是`(1, 0) 和 (0, 1)`怎么选？注意到这两种方案，结果这一位都是`1`
但区别在于，你选`(0 1)`的话，假设$$a > b$$，那么这一位`0 - 1`，会发生**向高位借位的行为**
这会使得$$a-b$$的结果尽可能小，于是贪心策略就是尽可能把`(1, 0)`改成`(0, 1)`
从高位到低位模拟就可以了

> 但是这里有一个坑点，最后一组样例没通过

坑点在于，经过我们上面的修改，**一定会发生借位行为**
当令$$a > b$$的时候，第一个$$a_i \neq b_i$$的位一定是`(1, 0)`，对这个位我们不需要任何修改
因为**这一位的`1`是给后面借位用的**

> 特别说明

位运算问题，还涉及到取值不能超过一个**上界的**，一般来说，需要**高位往低位考虑**

## CCPC Harbin 2024
**[A. Build a Computer](https://codeforces.com/gym/105459/problem/A)**
**问题描述**
给定区间$$[L, R]$$，要求构造一个边权都为`0, 1`的`DAG`，使得图上任意一条路径
对应的二进制表达，恰好对应区间$$[L, R]$$中的某个数

同时要求区间$$[L, R]$$上的数，都可以在图上找到**唯一的一条对应的路径**
路径的二进制表示不能有前导 0

输出构造的图

### 算法分析

> 考虑 $$[L, R]$$ 恰好形如`[000...0,  111...1]`怎么做？

假设`[000...0, 111...1]`有$$i$$位，那么对于每一位都要开一个节点
并且注意到对于每一个节点，下一位它既可以是 1，也可以是 0
用`bits(i)`表示二进制第$$i$$位对应的节点编号，开新节点的时候`bits[i] = ++tot`

**从低位到高位做**，如果某个位$$i$$的节点没开出来，就`bits[i] = ++tot`
然后对于`(bits[i], bits[i-1])`连权值为`0,1`的有向边

> 再复杂一点，$$[L, R]$$，其中$$L$$我们可以找到最高位为`1`的那个位`high(L)`
那么对于`[100...0,  111...1]`的情况如何处理

那很简单，对于$$[L, R]$$，我们找到那个`high(L)`的最高位，加一个**哨兵节点**`key`

先去构造`[000...0, 111...1]`，从**低位到高位构造**，构造完返回最高位的那个节点编号`id`
然后`(key, id)`连一条边权是$$1$$的边就可以

> 对于$$[L, R]$$中的其他情况呢？比如说**除了最高位的`1`**，剩下的后缀比如说是`0010110`

注意到对于$$L$$而言，最高位的`1`，再往下的位是`1`还是`0`是**确定的**
可以按照这种方法继续填`0`或者`1`的边，直到找到**次高位的 1**
这时候高位都可以不看，**从次高位的 1**开始构造，这就是一个**子问题**了

想到这里，思路基本就有了
就是先找到$$L$$最高位的 1，然后依次确定下一个更低的位是`0`还是`1`
直到找到次高位的`1`
此时扔掉更高的位，$$L \leftarrow L_1$$，递归构造$$L_1$$，以此类推

> 问题是，怎么实现这个递归构造

其实并不复杂
首先，找到$$L$$最高为$$1$$的位，并且将$$[L, R]$$划分成若干个形如`[00..0, 11...1]`的子区间
记为$$[le, ri]$$，每一个区间的**位数**记为$$i$$

从高位往低位**递归构造**，`build(le, ri, H)`
表示我们尝试构造区间$$[le, ri]$$中的所有数，（根据我们递归方法，`le, ri`**初始位数一定相同**）
并且当前只考虑**低 H 位**，返回值为构造出的连通块的节点编号

另外，注意到我们递归的时候，只考虑在低一位，即$$H-1$$位`or 上 1`，看看下一步边权是 0 还是 1
因此，每次递归的时候，对于**低 H 位**，都是形如`[00...0, 11...1]`

如果$$L \leqslant le \leqslant ri \leqslant R$$，注意到我们只考虑低 H 位
此时`[00...0, 11...1]`所有数都要构造出来，相邻点既要 0 的边又要 1 的边
线性构造就可以了，遍历$$[0, H)$$所有位，看看`bits(i+1)`存不存在

不存在就动态开点`++tot`，令`v = bits.back()`，$$\displaystyle tot \xrightarrow{0, 1} v$$，返回`tot`

其他情况，首先要动态开点`now = ++tot`，并且`H-1`位要么填 0，要么填 1，只能其中一种
考虑`mid = le | ( 1<<(H-1) )`，特别地，如果`H = 0`，说明此时`le, ri`只考虑最后一位不同
也就是说，此时`ri = le + 1`，这时候令`mid = le`
即`mid = H > 0 ? (le | (1 << (H-1) )) : le`

若$$L < mid$$，说明`H-1`位上铁定填上`0`
递归构造$$[le, mid-1]$$，即$$now \xrightarrow{0} build(le, mid-1, H-1)$$

若$$R \geqslant mid$$，说明`H-1`位上必须是`1`
递归构造$$[mid, ri]$$，即$$now \xrightarrow{1} build(mid, ri, H-1)$$

### 算法实现
```bash
void solve() {
    int L, R;
    cin >> L >> R;

vector<vector<pii> > G(maxn);
    vector<int> bits;

int tot = 2;
    int key = 1, nil = 2;
    bits.push_back(2);

auto high = [&](int x) -> int {
        vector<int> help(M+1, 0);
        for (int i = M; i >= 0; i--) {
            help[i] = (x >> i & 1);
        }
        for (int i = M; i >= 0; i--) {
            if (help[i]) return i;
        }
        return -1;
    };

auto linerbuild = [&](int H) -> int {
        int i = 0;
        for (; i < H; i++) {
            if ((int)bits.size() == i+1) {
                ++tot;
                auto v = bits.back();
                G[tot].push_back({v, 0}), G[tot].push_back({v, 1});
                bits.push_back(tot);
            }
        }
        return bits[i];
    };

auto build = [&](auto self, int le, int ri, int H) -> int {
        if (L <= le && ri <= R) {
            return linerbuild(H);
        }
        auto mid = H > 0 ? (le | (1 << (H-1) )) : le;

auto now = ++tot;
        if (L < mid) {
            auto id = self(self, le, mid-1, H-1);
            G[now].push_back( {id, 0} );
        }
        if (R >= mid) {
            auto id = self(self, mid, ri, H-1);
            G[now].push_back( {id, 1} );
        }
        return now;
    };

auto H = high(L);
    for (int i = H; i <= high(R); i++) {
        auto le = (1<<i), ri = (1<<(i+1))-1;

auto id = build(build, le, ri, i);
        G[key].push_back( {id, 1} );
    }

printf("%d\n", tot);
    for (int i = 1; i <= tot; i++) {
        printf("%d", (int)G[i].size());
        for (auto [ak, vk] : G[i]) printf(" %d %d", ak, vk);
        puts("");
    }
}
```

## Codeforces Round 983 (Div. 2)
**[D. Genokraken](https://codeforces.com/contest/2032/problem/D)**
**问题描述**，交互题，给你一棵树，形态未知，满足几个限制
第一就是根节点是 0，并且 0 接的每一个分支，都是一根链，不会有分叉
第二就是节点 1，除了它父亲是 0 之外，它下面一定要接一个儿子
第三就是对所有的点，如果$$x < y$$，那么$$pa_x < pa_y$$
你要问问题，然后推断树的形态

### 算法分析
![](/media/content_img/CF983D.png)
几个观察到的性质
首先，因为 `1` 一定要接东西，那么跟 `1` 同一层的节点，必定是`2, 3, 4,...`，直到放不下为止
其次，按照 bfs 一层一层接上节点，并且接节点的顺序是**从小到大的**
如果中间跳过了某些节点没有接东西，之后这些点也都不可能再接东西了

根据这些性质，可以去模拟
1）从`i = [2...n]`依次询问`ask(1, i)`，看看第一个和`1`同链的节点`k`
也意味着`[2...k-1]`都是第一层的节点（先放第一层，直到放不下为止）
后续我们的策略选择这些**可以接的点中，最小的一个**，接后续的节点
这一步在做的过程中，可以用小根堆维护

2）怎么确定`[k+1...n]`节点在什么位置呢？实际上只需要暴力检查这些节点
因为小根堆中，被跳过的节点，后续是没有用的，一个点最多只会出堆一次
那么为每一个`i = [k+1...n]`找到**它应该接的点**，就可以了
做法就是从小根堆中找最小的，看他能不能接上`i`，找到了，就继续检查`i+1`
之后，不论找没找到，小根堆这个`top`的点是不会后续继续被用到的，直接`pop`掉

## 换根 dp 问题
来看一下换根 dp 的一些经典问题
**[积蓄程度](https://www.acwing.com/problem/content/289/)**
树形水系，每条边有容量$$c(x, y)$$，另外，度数为$$1$$的点是汇点，有一个节点是源点
现在问哪个节点作为源点时，水系的流量最大

### 算法分析
**换根 dp 的信息维护，两遍 dfs**
![](/media/content_img/changeroot.png)

第一次 `dfs(u)`，如果$$v$$不是汇点，那么$$dp(u) = \sum_v \min(dp(v), c(u, v))$$
如果是汇点，那么$$dp(u) = c(u, v)$$

第二次`dfs2(u)`，根据`u`的信息维护出`v`的
如果`u`是汇点，那么$$dp2(v) = dp(v) + c(u, v)$$
如果`v`是汇点，那么$$dp2(v) = dp(v) + \min (c(u, v), \quad dp2(u) - c(u, v))$$
如果`u, v`都不是汇点，那么先计算出实际流过$$(u, v)$$边的流量
令$$flow = \min(dp(v), c(u, v))$$，从而$$dp2(v) = dp(v) + \min(c(u, v), \ dp2(u)-flow)$$

```bash
void solve() {
    vector<ll> dp(n+5, 0);
    auto dfs1 = [&](auto &dfs1, int u, int fa) -> void {
        for (auto [v, w] : G[u]) {
            if (v == fa) continue;
            dfs1(dfs1, v, u);
            // 可能流不满，所以非叶子结点，要取 min
            if (G[v].size() == 1) dp[u] += 1LL * w;
            else dp[u] += min(dp[v], 1LL * w);
        }
    };
    dfs1(dfs1, 1, 0);

vector<ll> dp2(n+5, 0);
    dp2[1] = dp[1];

auto dfs2 = [&](auto &dfs2, int u, int fa) -> void {
        for (auto [v, w] : G[u]) {
            if (v == fa) continue;
            // 可能流不满，换根的时候，要记得和 c(u, v) 取一个 min
            if (G[u].size() == 1) dp2[v] = dp[v] + 1LL * w;
            else if (G[v].size() == 1) dp2[v] = dp[v] + min(1LL * w, dp2[u] - w);
            else {
                auto flow = min(dp[v], 1LL * w);
                dp2[v] = dp[v] + min(1LL * w,  dp2[u] - flow);
            }

dfs2(dfs2, v, u);
        }
    };
    dfs2(dfs2, 1, 0);
}
```

## 2024 百度之星 换根 dp
**[小度挪车](https://www.matiji.net/exam/brushquestion/21/4498/F16DA07A4D99E21DFFEF46BD18FF68AD?from=1)**
给定一个$$n$$个点的树，每个点都有一辆车，每一辆车要么是粉色的，要么是其他颜色的
现在需要把所有粉色的车都停在一起，然后剪掉一条树边，使得粉色车在一个连通块，其他颜色的车在另一个连通块
剪切树边不消耗时间，但交换**相邻**节点上的车需要一个单位时间，问最少要几个单位时间，无解输出`-1`

### 算法分析
> 先考虑什么时候无解

可以`dfs`一遍，对于每个节点$$u$$，分成两部分，分别是`( sz[u], n - sz[u] )`
另外我们还知道`0, 1`的个数分别是`cnt0, cnt1`，如果`(sz[u], n - sz[u]) == (cnt0, cnt1)`
或者`(sz[u], n - sz[u]) == (cnt1, cnt0)`，那么就有解，否则就无解

> 这启发我们用类似换根的做法，进行树形 dp

那么不难想到，只要对每个点，维护`(sz(u), n - sz(u))`分别改成`(cnt0, cnt1)`和`(cnt1, cnt0)`需要的**最小时间**即可

> 现在的难点，就在于如何计算`u`及其子树`sz(u)`，全部改成`0 or 1`，所需要的代价

遍历$$u$$的所有子树，假设当前考虑子树$$v$$，要把子树$$v$$中所有的`0`挪出去，代价怎么算呢？记代价为`move0`
实际上，我们只需要考虑**子树`v`中的每一个`0`**，把子树单独抽出来
那么把每个`0`移出子树的代价，是`dep + 1`，其中深度从`0`开始计算

那么把子树`v`全部变成`0`的代价，就是$$\sum_v (dep_v + 1)$$，其中要求`v`的颜色是`0`

> 简单点说，就是**子树`v`中 0 节点的相对深度和**，相对深度针对子树的根`v`
每一个子节点，让他往 LCA 或者祖先 v 走，需要**向上走多少步？**这可以在向父亲合并的时候，递推求出来

`move0(v) = (v子树中，颜色是 0 的节点的深度和) + (颜色是 0 的节点的个数)`

这个很好计算，颜色是`0`的节点个数一遍 dfs 就可以求出来，至于深度和有 2 种算法
第一种就是，对`dfs`序打表，`dep[ l(v) ]`可以一边 dfs 一边求，这样可以打表出子树`v`每个节点的深度
然后求一遍前缀和，`move0(v) = ( [l(v), r(v)]节点的深度和 ) - (节点 0 的个数) * ( dep[ l(v) ] - 1 )`

还有一种求法是，**根据子树来递推**
对于$$u$$的每一棵子树$$v$$，`move0(v)`表示子树`v`中，颜色是`0`的所有节点的深度和
那么`move0(v) --> move0(u)`，朝父亲转移的时候，原来子树`v`中所有 0 节点的深度都会`+1`
所以有递推`move0(u) += move0(v) + (v 子树中 0 的个数)`

那么和`1`有关的信息，也是类似维护，不再赘述

> 知道了这些信息，怎么求最优解？

![](/media/content_img/astar2024.png)

只需要第二遍 dfs，额外维护出**朝上的子树**那一部分信息即可
```bash
upsz0(v) = cnt0 - sz0(v)
upmove0(v) = upmove0(u) + { move0(u) - move0(v) - sz0(v) } + upsz0(v)
```
第三遍`dfs(u)`的时候，就可以考虑每个`(u, v)`了
```bash
if sz(v) == cnt0:
	res = min(res, move1(v) + upmove0(v))
if sz(v) == cnt1:
	res = min(res, move0(v) + upmove1(v))
```

### 算法实现
```bash
void solve() {
	// 其余代码省略
    // pink 0, other 1
    int cnt0 = 0, cnt1 = 0;
    for (int i = 1; i <= n; i++) {
        if (str[i] == 'P') cnt0 += 1;
        else cnt1 += 1;
    }

// dfs1
    vector<int> sz(n+1, 0), sz0(n+1, 0), sz1(n+1, 0);
    vector<ll> move0(n+1, 0), move1(n+1, 0);

auto dfs1 = [&](auto &dfs1, int u, int fa) -> void {
        sz[u] = 1;
        str[u] == 'P' ? sz0[u] = 1 : sz1[u] = 1;
        
        for (auto v : G[u]) {
            if (v == fa) continue;
            dfs1(dfs1, v, u);

sz[u] += sz[v], sz0[u] += sz0[v], sz1[u] += sz1[v];
            move0[u] += move0[v] + sz0[v];
            move1[u] += move1[v] + sz1[v];
        }

assert(sz1[u] + sz0[u] == sz[u]);
    };
    dfs1(dfs1, 1, 0);

vector<int> upsz0(n+1, 0), upsz1(n+1, 0);
    vector<ll> upmove0(n+1, 0), upmove1(n+1, 0);

auto dfs2 = [&](auto &dfs2, int u, int fa) -> void {
        for (auto v : G[u]) {
            if (v == fa) continue;

upsz0[v] = cnt0 - sz0[v], upsz1[v] = cnt1 - sz1[v];
            upmove0[v] = upmove0[u] + ( move0[u] - move0[v] - sz0[v] ) + upsz0[v];
            upmove1[v] = upmove1[u] + ( move1[u] - move1[v] - sz1[v] ) + upsz1[v];

dfs2(dfs2, v, u);
        }
    };
    dfs2(dfs2, 1, 0);

ll ans = inf;
    auto dfs = [&](auto &dfs, int u, int fa) -> void {
        for (auto v : G[u]) {
            if (v == fa) continue;
            dfs(dfs, v, u);

if (sz[v] == cnt0) chmin(ans, move1[v] + upmove0[v]);
            if (sz[v] == cnt1) chmin(ans, move0[v] + upmove1[v]);
        }
    };
    dfs(dfs, 1, 0);
    if (ans == inf) ans = -1;
}
```

## AtCoder Beginner Contest 378
### E
**[Mod Sigma Problem](https://atcoder.jp/contests/abc378/tasks/abc378_e)**
**问题描述**
```math
\displaystyle
\sum_{1 \leqslant l \leqslant r \leqslant N} \left( (\sum_{l \leqslant i \leqslant r} A_i) \bmod M) \right)
```
**算法分析**
先考虑一下答案有什么形式
不难发现，最后的答案是，形如$$r \in [0, M-1]$$的若干个数$$r_1 + r_2 + \cdots$$求和

对于$$(S\_r - S\_{l-1}) \bmod M$$，考虑怎么在遍历$$r$$的时候，对每个确定的$$r$$
维护出相关信息
记$$S_r = kM + rem$$，前缀可以有如下形式

记为$$(k\_0M + d\_0), (k\_1M +d\_1),\cdots, (k\_{r-1}M + d\_{r-1})$$
如果$$d\_0, d\_1, \cdots, d\_{r-1}$$都$$\leqslant rem$$
那么答案就是$$(rem - d\_0) + (rem - d\_1) + \cdots + (rem - d\_{r-1})$$

现在问题是，有一些数可能会$$> rem$$，这个怎么办呢？
**每一个数都补加一个**$$M$$就可以了，扫描同时，用树状数组维护值域
看看$$[rem+1, M]$$之间有几个数？这可以用树状数组快速实现，假设有$$cnt$$个数
在上述结果中，$$+ cnt \cdot M$$即可

### F
**[F - Add One Edge 2](https://atcoder.jp/contests/abc378/tasks/abc378_f)**
**问题描述**
给定一棵树，树加一条边会成为一个图，这个图有且只有一个环
问有多少种这样的图，满足以下性质
第一，图是简单的，没有重边和自环，第二，环上的点的度数恰好为`3`

**算法分析**
想倒是不难想，假设需要加一条边$$(u, v)$$，那么必须满足$$deg_u = 2, deg_v = 2$$
同时，$$(u, v)$$路径上的所有的点，$$deg = 3$$，问题是，怎么统计出来呢？

不妨用$$dp(u)$$表示$$u$$及其子树中，有多少个`deg = 2`的点
同时，这些点还必须满足，任意两个`deg = 2`的点，路径上的点`deg = 3`

这个限制不难满足，`dfs(u)`的时候，如果`deg(u) == 2`，那么令`dp(u) += 1`
同时，**只在`deg(u) = 3`的点处，挂载儿子的 dp 值**，`if (deg(u) == 3)  dp(u) += dp(v)`
而其他`deg`值，可以直接舍弃儿子的 dp 值，**不转移儿子的 dp 值**

接下来就可以统计信息了，对于$$v \in G(u)$$
1) 如果`deg(u) == 2`，那么最终的环**不是跨分支的**，只需要在`v`及其子树中，任选`deg = 2`的点就可以了
值得注意的是，如果`deg(v) = 2`的话，就是重边了，也不满足题目要求
所以，答案是`ans += ( dp(v) - (deg(v) == 2) )`

2）如果`deg(u) == 3`，那么就涉及到跨分支统计了
我们用`sum`记录一下前缀分支中，`v`及其子树中有多少个`deg = 2`的点
这时候`ans += sum * dp(v)`即可

3）遍历分支`for v in G(u)`的时候，计算完成后统计`sum += dp(v)`
当且仅当`deg(u) == 3`的时候，`dp(u) += dp(v)`

最后返回前，子树都计算完成了，看一下`u`的`deg`是否为`2`即可，`dp(u) += ( deg(u) == 2 )`

上一篇：2024-11月一些算法比赛（一）下一篇：积性函数，莫比乌斯反演（二）

看完文章有啥想法