集训之搜索与动态规划专题

A

题目简介

给你一个 $n$ 个点，$m$ 条边的 DAG，每条边有一个权值，经过一条路径就可以形成一个字符串，$q$ 个询问，询问从 $u$ 出发第 $k$ 大字符串的终点在哪。

题目分析

首先考虑暴力做法，即是处理 $dp$ 数组，代表每个点向后走能形成多少个字符串，递推公式显然为 dp[u] += dp[v] + 1。然后询问即是试探每个儿子走，如果不走当前儿子，就减去当前儿子贡献，试探下一个儿子。暴力复杂度为 $O(qn)$。

考虑优化走的过程。因为是 DAG，可以考虑重链剖分来优化走重链的过程。先考虑在此种情况下重链剖分的复杂度是否有保证。考虑同样用 siz 大小划分，但这里 dp 和 siz 递推方程类似，考虑用 dp 数组替代。发现同样满足走轻边，至少减半的性质，即仍是 $log(n)$ 复杂度。

先考虑具体优化过程，发现即是要预处理一个倍增跳会让 $k$ 值减少多少，跳一次重儿子显然即是前面儿子的 $dp$ 值的和加上当前这条边的贡献 $1$，而剩下的 DP 就好。

现在已经考虑了跳重链的优化，但如果每次选择的是偏后面的轻儿子是会卡成 $O(n^2)$ 的，所以还要考虑对轻儿子选择的优化。发现一个简单的二分就可以。

可能写炸的点：

1. 爆 long long，如果与一个极大值取 min 很可能影响重儿子的选择，导致复杂度假了。所以可以考虑用 double。
2. 跳重链跳的条件，需要是在一个范围内，而不只是只有一个下限。

B

题目简介

给你一个 $n \times n$ 的矩阵，每个点都有一个权值，选择了一个点，就不能选择另外一些点，求选择的最大值。

题目分析

注意到选择限制是上下对称的，意即如果上面的选择影响到下面的选择，那么下面的选择也会影响到上面的选择；而如果上面的选择没有影响到下面的选择，那么下面的选择也不会影响到上面的选择，所以纵向来看是不用考虑后效性的。

再从横向来看，几个点互相影响，且 $n \le 8$，显然可以预处理出横向的所有合法选择。

现在就可以枚举每行的状态来搜索，但还是会超时，考虑优化。

一个显然的剪枝就是统计合法的状态中最大的后缀和，如果当前的搜索加上最大的后缀和仍小于最大值就可以不用搜索了。发现加上这个剪枝就可以过了。

C

题目简介

给你 $n$ 个数，求最长的严格单增然后严格单减的长度。

题目分析

显然可以枚举每个单峰的峰点，然后对这个峰点求最长的单调递增长度和单调递减长度即可。

普通的求 LIS 的 DP 方法是 $O(n^2)$，显然会超时。但 $dp[i] = \max\limits_{j < i \land a[j] < a[i]}(dp[j] + 1)$，即求最大值，显然可以用线段树优化，$j < i$ 从前往后递推本来就保证，考虑 a[j] < a[i] 即可，发现可以让 a[j] 作为线段树的下标，然后查询区间 $[1, a[i] - 1]$ 的最值即可。求单调递减长度同理。

用线段树优化的时间复杂度 $O(nlog(n))$

D

题目简介

给你 $n$ 个数，每个数可以进行一次操作，操作如下：

1. 变为 0
2. 不变
3. 变为 $2^{a_i}$
4. 变为 $a_i!$

其中 $3$ 和 $4$ 操作最多进行 $m$ 次。求最终和为 $S$ 的概率。$(1 \le m \le n \le 24)$

题目分析

先考虑总方案数的数量，即是枚举 $m$ 的操作次数，即 $\sum\limits_{i = 0}^{m}{C_{n}^{i} \times 2^i \times 2^{n - i}}$。

再考虑如何搜索方案数，直接暴力搜复杂度 $O(4^n)$，无法接受。

但此题初末状态是一定的，即可以 meet in the middle，考虑双向搜索。即以初始状态搜 $\dfrac{n}{2}$ 步长，以末状态搜 $\dfrac{n}{2}$ 的步长。复杂度大约为 $O(2^{n + 1})$ 方，在可接受的范围内。

具体就是在第一次搜索过程中保存当前进行多少次 $3$ 和 $4$ 操作的情况下得到的值。第二次搜索再调用第一次搜索的结果来计算答案即可。可以用 map，也可以用 hash。

E

题目简介

给你 12 个数，求将其分成最多个三角形的方案数。

题目分析

数字很小，考虑爆搜。首先考虑如何搜索不重不漏，可以考虑增加搜索限制，先将序列排序，以元素处于序列的位置作为大小比较，我们要求前一组的第一个元素小于后一组的第一个元素，组内的元素单增，且只有搜索完前一组才搜索后一组，这样就可以做到不重不漏。

现在考虑如何具体搜索，注意到如果增加限制后，一组中的三角形可能情况数量只有 $C_{12}^3$ 种，可以提前预处理出来。可以更近一步，预处理出确定第一个数后，可能的第二个数以及可能的第三个数有哪些。剩下就可以愉快爆搜了。

F

题目简介

给你 $n$ 个长度为 $l$ 的字符串，开始随机选择一个字符串作为目标字符串。之后你可以选择一个位置然后知道这个位置的答案，已选择的位置不能再被选择，当能确定目标字符串时就不再选择。请问选择的次数的期望值为多少。

题目分析

题目所求可以转化为考虑每个字符串的在每种情况下选择的长度除以方案数和字符串数。分母可表示为 $l!n$，先考虑分子。

首先可以枚举初始选择的字符串是哪一个，而选择情况可以用状压表示，那么现在的复杂度就是 $O(n2^l)$，也就意味着我们最好要在 $O(1)$ 的情况下处理一个搜索状态。

而计算一个搜索状态的贡献，一个显然的想法就是从前往后枚举到哪个点就可以唯一确定一个字符串。这个可以对每个字符串预处理一个选择当前位可以排除掉哪些字符串（状压）的数组，但即使这样预处理复杂度也是 $O(l)$ 的，我们还能更快地处理一个状态地贡献吗？

我们对于每个状态都是从前往后扫，这是很浪费的，我们不妨将每次的排除字符串的状态存起来，用状压 DP 递推的方式来优化时间复杂度。

即假设当前状态为 x，那么由 $x - lowbit(x)$ 我们就可以快速继承之前的结果，只要处理 $lowbit(x)$ 排除的字符串即可。但注意到是要求第一个位置能排除所有字符串的位置，所以我们再用一个数组记录每个可以排除所有字符串的状态的第一个位置即可。

现在就可以通过状压 DP 的方式达到 $O(1)$ 的复杂度处理单个搜索状态了。

G

题目简介

给你一个初始全为 0 的长度为 $n$ 的序列，给你 $m$ 个形如增加区间 $[l_i, r_i]$ 的数 $x_i$ 的操作，你可以任意选择这些操作，求经过这些操作后可能的最大值。

题目分析

首先可以枚举这个最大值的位置，显然是只有区间包含这个数的才起作用，且如果这个点为最大值，可以只考虑这些包含这个数的操作，其他操作不影响。

暴力考虑可以搜索也可以背包 DP。考虑用背包 DP 记录答案。但直接暴力显然会超时。

考虑到操作是对区间的影响，所以可以用扫描线的方式在每个操作的起点放一个增加标志，在每个操作的终点的后一个位置放一个减少标志。增加显然就是普通的背包，而减少呢？就是回退背包。

回退背包需要将记录是否可行改为记录方案数，考虑到方案数很大，所以可以考虑选择一个合适的模数。而回退的过程其实就是逆过程，也可以从 DP 状态的含义思考。dp[j] = (dp[j] - dp[j - a[i]] + MOD) % MOD，如果 dp[j - a[i]] 已经是表示不考虑 a[i] 的方案数，那么从含义来看正确性显然，但为了保证 j - a[i] 是不考虑 a[i] 的方案数，需要从前往后枚举 j。

H

题目简介

给你 $n$ 个点的树，每条边随机消失，求消失后最大的连通块的直径（最远的两个点的距离）小于 $m$ 的概率。

题目分析

关于链的长度问题可以将其转化为根节点考虑，即是对于任意根节点的两条不同最长链的长度和小于 $m$。为此，我们可以设计一个 DP 数组，dp[u][k] 代表 $u$ 为根节点的最长链（指一端是 $u$）为 $k$ 且满足子树最长链（端点任意）小于 $m$ 的方案数。

对于每个儿子，显然有两种情况，一种是切掉连边，另一种是不切掉连边。

对于切掉连边有：

$dp[u][i] = dp[u][i] \times \sum\limits_{j = 0}^{m}dp[v][j]$

对于不切掉连边有：

$dp[u][max(i, j + 1)] = dp[u][i] \times dp[v][j]$

注意各个情况的枚举上界，以及前后 $dp[u]$ 代表的含义不同，应该先将之前的 $dp[u]$ 的状态另存起来，用此来递推新的 $dp[u]$。

此复杂度为 $O(n^2m)$，显然会超时。

但注意到 DP 状态与深度有关，可以考虑长链剖分优化成 $O(nm)$。

长链剖分的优化思路是对于重儿子（有最长链）通过指针的方式可以直接继承（因为只是相差 1），而对于轻儿子则直接原来一样暴力转移，但转移的深度（即上面的 $j$）可以根据轻儿子的深度来定。这些转移的深度和即是所有长链的长度和，而所有长链长度和即是 n（这里长度定义为点数）。即总转移次数为 $O(n)$。

所以学一下长链剖分优化上述 DP 过程即可。

I

题目简介

给你 $l$, $r$, $m$，求区间 $[l, r]$ 内优美数的和。优美数的定义为一个数中在十进制下各个位出现的不同数字的个数不超过 $m$。

题目分析

显然的数位 DP。但此题求和，所以记忆化不仅要记忆化方案数，还要记忆化和。

dfs 数位 DP。用 limit 代表是否贴界，用 lead 表示是否仍有前导零。再用一个数字状压当前出现数字的集合即可。

如数位 DP 的模板一样，但返回二元组，第一个返回方案数用于算当前选择数字的贡献，第二个返回后续的和即可。

J

题目简介

给你一颗 $n$ 个点的树，每条边有一个边权。问从每个点出发到达根节点 $1$ 所需要的时间。时间计算方式为，到达一个结点后，你可以选择等待 $t_i$ 时间，然后以速度 $v_i$ （速度定义为走单位长度所需要的时间）前进，也可以仍以原来的速度前进。

题目分析

考虑树上 DP，即有两种情况，在一个点等待，或不等待（第二种情况在实现上可以归结为第一种）。而 DP 转移即是枚举第一个等待的点。

$dp[u] = dp[x] + (dis[u] - dis[x]) \times v[u] + t[u]$

考虑变形为

$dp[u] - t[u] - dis[u] \times v[u] = dp[x] - dis[x] \times v[u]$

显然是一个斜率优化 DP 的例子。

令 $b = dp[u] - t[u] - dis[u] * v[u]$，$y = dp[x]$，$x = dis[x]$，$k = v[u]$。

分析一下，发现是横坐标单调，$k$ 不单调的情况。即是需要在原斜率 DP 的基础上二分转移点。

但这是在树上，由一条链转到另一条链需要回退信息。

考虑到增加当前结点只会实际修改一个点（删除后续点实际上并没有修改），转移了一下双端队列的尾结点。即实际改变的值只有两个，所以可以暴力存起来这两个值，再回退即可。

一个比较坑的点：如果用乘法比较斜率会爆 long long

K

题目简介

给你一个集合，一开始只有 $1$，你可以不断进行以下操作选择集合中任意两个数（可以相同），作和并加入集合或作差将其绝对值加入集合。求使 $n$ 加入集合的最小操作数。

题目分析

考虑到是最小操作数，且上界不确定（但可以构造出一个上界），可以考虑迭代加深。迭代加深的搜索数只有 $bfs$ 的两倍左右，且能很好地记录当前搜索状态。

直接搜过不去。但显然每次操作一定是操作新得到的数，否则新得到的数没有意义（可以证明如果是后续对其操作可以转化为一开始就对其进行操作）。

但还是过不去。考虑另一个优化：如果当前得到的最大的数后续进行都是连续翻倍操作仍是小于 $n$ 的那显然不行。

思考一下，这个看似没有多大优化的优化其实能极大减少搜索树。加入这个优化即能过。

千万不要 hash，状态数太多了，hash 冲突卡的死死的 :(

L

题目简介

求哈密顿路径的最小值。

题目分析

状压 DP 即可。用一个数字代表现在已经经过了哪些点。递推时枚举现在在哪个点，是由哪个点转移而来的即可。

M

题目简介

给你 $n$ 个数，问是否存在一个 $n$ 个结点的 BST，将这 $n$ 个数作为权值，且相邻两个结点的和满足 $0$ 与 $1$ 的个数差不超过 $m$。

题目分析

首先可以预处理出哪两个点可以连边。但如何构造呢？

其实只要知道 BST 的子树容易用数组的连续一段来表示，即可以转化为区间问题就简单了。

首先权值排序，根据 BST 的性质，子树可以转化为区间的连续一段，且子树的父亲一定是区间紧挨着的两端的数。

为了方便，我们用 $dp[l][r][0]$ 代表区间 $[l + 1, r]$ 形成了一颗树，且以 $l$ 是这棵树的根结点的父亲，$dp[l][r][1]$ 代表区间 $[l, r - 1]$ 形成了一棵树，且 $r$ 是这棵树的根节点的父亲。

考虑递推 dp[l][r][0] |= (dp[l + 1][j][1] & dp[j][r][0] & can[l][j])，can 数组即是前面预处理是否可以连边。

dp[l][r][1] 同理。

初始状态：dp[i][i][0] = dp[i][i][1] = 1

最终答案即是检验是否存在一个 $k$ 满足 dp[1][k][1] && dp[k][n][0] 即可。

时间复杂度为 $O(n^3)$。

N

题目简介

给你一棵 $n$ 个点的树，每个边有边权，求每个点到其他点的最远距离。

题目分析

上个专题不是有类似的吗（

树形 DP。

考虑两次 dfs，第一次 dfs 处理最长链长度，以及最长链是由哪个儿子贡献出来，次长链由哪个儿子贡献出来。

第二次 dfs 统计答案。考虑一个点能到达的最远点，要么是在自己子树中，这已经在第一次 dfs 中处理出来了，要么是经过了父亲结点。而经过父亲节点的情况可以从 dfs 过程从上往下传参来得到。具体是有两种情况，第一种是父亲结点的其他儿子子树中得到，这种情况可以从第一次 dfs 得到的儿子来处理；第二种情况是经过父亲的父亲，这其实就是父亲结点 DP 时从上面传下来的参数，直接用即可。

两次 dfs 即可，时间复杂度 $O(n)$。

O

题目简介

给你一颗 $n$ 个结点的树，每个点有一个点权，定义两个点之间的花费为 $a_i \cdot a_j \cdot dis^2(i, j)$，现在需要你对每个点 $i$，求 $\sum\limits_{j = 1}^{n}cost(i, j) \mod 998244353$ 的值。

题目分析

如果只是对根节点求答案，那很容易 $O(n)$ dfs 即可得到。但现在是对 $n$ 个点，考虑是否能由根节点递推其他点，即换根 DP 来做。

考虑根节点 $u$ 向子节点 $v$ 移动，那么 $v$ 的子树内的 $dis$ 值会减少 1，而其他点的 $dis$ 会增加 1。

考虑减少 1 的情况（在此之前可以先省略 $a_i$，因为 $a_i$ 可以最后输出答案时再乘以）

$\sum\limits_{j \in substree(v)}a_j\cdot (dis - 1)^2 = \sum\limits_{j \in substree(v)}(a_j \cdot dis^2 + a_j - 2a_jdis)$

对于增加 $1$ 的情况：

$\sum\limits_{j \notin subtree(v)}(a_j \cdot dis^2 + a_j + 2a_jdis)$

如果令 ans[i] 代表所要求的答案，sum[i] 代表以 1 为根子树的权值和，g[i] 代表以 $i$ 为根时子树结点 $i \cdot a_i$的权值和，f[i] 代表以 1 为根时的子树结点 $i \cdot a_i$ 的权值和，all 代表所有结点的权值和。

则两者相加可表示为：

$ans[i] + all + 2(g[i] - f[j] - sum[j]) - 2(f[j] + sum[j]) = ans[i] + all + 2g[i] - 4f[i] - 4sum[j]$

f[i] sum[j] 很好处理。而 g[i] 也只需要简单的递推：

g[j] = (f[j] + g[i] - f[j] - sum[j] + all - sum[j]) = g[i] - 2sum[j] + all)

所以就是第一遍处理 f sum ans[1] 即可。

第二遍 dfs 按照上述公式处理 ans g 即可。

P

题目简介

给你 $n$ 个数，你需要将其分成两半，使得两半的差值的绝对值最小。你还可以对每个数进行一次翻倍的操作。

题目分析

分成两半，如果将加入第一个集合视为加，第二集合视为减，那么就可以用背包处理。发现翻倍操作也可以加入到背包处理中。即是一个典型的分组背包，对于每个数 $a_i$ 有四种选择：

1. $a_i$
2. $-a_i$
3. $2a_i$
4. $-2a_i$

剩下就是对每个数进行分组背包，最后看哪个可行的最接近 0。

因为下标不能为负数，可以考虑整体后移 $20000$ 位解决。

Q

题目简介

题目分析

此题典型公平组合游戏，搜索是否为必胜，必败状态即可。

当 $x^y \cdot z > n$ 时，即为搜索边界，为必胜状态。

注意到 𝑛 的范围较小，且 $x \ge 2$，这意味着当 $y > 20$ 时，不管 𝑥, 𝑧 的具体取值如何，必然是必胜状态。所以只需考虑 $y \le 20$ 的情况。

再注意到指数爆炸增长的性质，即 $y \ge 2$ 时，$x \le 1000$，且 $y$ 越大，$x$ 的范围越小；且 $y = 1$ 时的状态有限。所以我们可以对 $y = 1$ 时直接进行爆搜。而记忆化 $y \ge 2$ 时的大部分状态，其他状态也爆搜。

测试记忆化 $y \ge 2, x \le 1000, z \le 1000$ 的状态即可通过此题。

注意到 $y \le 20, z \le 10^6$ ，$y$, $z$ 固定，则 $x$ 上限也固定，所以可以考虑预处理 $x$ 在指定 $y$, $z$ 下的取值上限来优化一下搜索常数。

此外还可以让 2，3 操作的优先级更高来使数字增长更快来优化。

R

题目简介

$n$ 给你 $n$ 个点，每个点有自己的权值，且有自己的类型，对于第 $t_i$ 个类型，只能从其左边 $k_i$ 个点到达。询问到达终点的最大权值为多少。

题目分析

写出 DP 方程

$f[i] = \max\limits_{j = i - k_i}^{i - 1}f[j] + a[i]$，考虑线段树（不是

因为选择长度是固定的，且点的类型小于等于 3，所以可以对每个点类型都建一个单调队列来优化 DP。

S

题目简介

给你 $n$ 个 01 串，问是否存在一种选择方案使得它们的并集全为 1，两两交集为 0。

题目分析

爆搜（不是

如果知道舞蹈链的话，那就是板子题。所以说学一下舞蹈链即可。

舞蹈链是一种用双向循环链表维护 1 的算法。

不断找有 1 的行删除（先选择一列中 1 的数量少的删除来减少分支数），删除这一行还要删除拥有这一行其他 1 的行（不能选了）。删除操作因为是在链表上执行所以很快。回溯逆序操作即可。

T

题目简介

给你四个序列，序列 $a$ 满足 $a_i = A \times a_{i - 1} + B$，序列 $b$ 满足 $b_i = C \times b_{i - 1} + D$，序列 $c$ 满足 $c_i = a_i \times b_i$，序列 $d$ 满足 $d_i = d_{i - 1} + c_i$。询问序列 $d$ 的第 $n$ 项。

题目分析

很容易想到用矩阵乘法来递推（推通项计算太强了），而且矩阵乘法也很好表示：

剩下就是用矩阵快速幂算即可。

U

题目简介

给你 $n \times n \times n$ 个点，每个点有一个权值，每次询问体积为 $V$ 的权值最大值。

题目分析

显然是可以用前缀和来算的。但没想到不会超时 :(。

预处理前缀和复杂度 $O(n^3)$。

回答询问时，枚举体积所有可能的三维长度再暴力枚举一个端点用前缀和算即可，复杂度 $O(kQn^3)$，$k$ 是体积 $V$ 能分解成多少种情况，算了一下最坏的情况 $k$ 可以达到 63。但因为很多 $n^3$ 都没跑满，所以说没有是预想的超时。

至于前缀和，简单容斥可以得到这样递推：

询问答案这样：

V

题目简介

LCS 但可以改变一个字符串的 $k$ 个字符版($0 \le k \le 20$)。

题目分析

改变字符其实就是在原来的基础上增加一个维度，并且增加一个递推方程即可。

递推方程增加的是：dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1])，正确性显然。

原来的递推方程是：

dp[i][j][k] = dp[i - 1][j - 1][k] (s1[i] == s2[j])

dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k])

用这三个递推方程递推即可，复杂度 $O(n^2k)$。

W

题目简介

给你 $n$ 个点，每个点有两个权值 $x_i$ 和 $y_i$，对于每个 $i$，求最大的 $\sqrt{|x_j-x_i|} + y_j - y_i$

题目分析

首先可以取出 $y_i$ 最后答案减去即可。然后考虑去掉绝对值，考虑 $x_i > x_j$ 的情况，即是求 $\max(\sqrt{x_i - x_j}+y_j)$，即是求 $-\min(-\sqrt{x_i-x_j}-y_j)$，用四边形不等式验证，或者用四边形不等式的性质（凸函数和里面是一个四边形恒等式）可以发现这是满足四边形不等式的。

所以说由四边形不等式可以得知满足决策单调性，剩下就可以整体二分解决。

上面是只考虑 $x_i > x_j$ 的情况，逆序再做一遍相同的过程即是 $x_i < x_j$ 的情况。

X

题目简介

题目分析

很容易想到 DP，DP 方程也很好写。

有两种情况，一种是当前点 $i$ 正面是最小值，另一种情况是 $i$ 正面不是最小值。

发现这取决于前面比 $i$ 小的数，很容易想到用单调栈来维护前面比 $i$ 小的数有哪些，如果当前 $i$ 更小，那么之前正面比 $i$ 大的数必然没有贡献，所以维护一个正面数字单调的单调栈即可。

发现如果枚举上一个组合的最后一个元素，那么对于第一种 dp[i] 可以由区间 $[stk[top], i - 1]$ 递推而来

$dp[i] = \max\limits_{j = stk[top]}^{i - 1}(dp[j]) + a[i]$，而取 $\max$ 操作用线段树即可。

而对于第二种情况，按照 $i$ 区间所增加的权值是哪一个，可以由 $[stk[top - 1], stk[top])$ $[stk[top - 2], stk[top - 1])$…递推而来。

分别是 $dp[i] = \max\limits_{j = stk[top - 1]}^{stk[top] - 1} + a[stk[top]]$, $dp[i] = \max\limits_{j = stk[top - 2]}^{stk[top - 1] - 1} + a[stk[top - 1]]$…

但其实并没进行第二个方程之后的必要，因为在处理 dp[stk[top]] 的时候已经考虑了第二个方程之后的情况。所以真正有用的只有第一个方程。

综上，对于每个 $i$，都讨论两种情况用线段树查询最值来递推即可。

Y

题目简介

给你 $n$ 个数，求最长连续子段 $a_l, a_{l + 1}, a_{l + 2},…,a_r$ 使得 $\sum\limits_{i = l}^{r}(i - l + 1) \cdot a_i$ 最大。

题目分析

考虑化简式子，令 $b_i = \sum\limits_{j = 1}^{i}ja_j$, $sum_i = \sum\limits_{j = 1}^{i}a_j$

$$f_i = b_i - b_{l - 1}+(1- l) \cdot (sum_i - sum_{l - 1})$$

考虑式子化简，令 $l - 1 = j$，则

$$f_i = b_i - b_j - j \cdot sum_i + j \cdot sum_j$$

移项，得

$$f_i - b_i = -b_j + j \cdot sum_j - j \cdot sum_i$$

令 $b = f_i - b_i$, $y = -b_j + j \cdot sum_j$, $x = j$, $sum_i = k$

则是一个典型的斜率优化的例子，发现斜率不单调，但横坐标单调，所以可以在原来的单调队列基础上变为二分决策点即可。

Z

题目简介

求一棵树的最大独立集但点权会变。

题目分析

最大独立集是很好求的，用状态

f[u][0] 表示不选择当前结点子树最大独立集，f[u][1] 表示选择当前结点子树的最大独立集，则有

$$f_{u, 0} = f_{u, 0} + \max(f_{v, 1}, f_{v, 0})$$

$$f_{u, 1} = f_{u, 1} + f_{v, 0}$$

但此题会变，如果变一次就全部重新 DP，那么复杂度不可接受，考虑优化 DP。

重链剖分，并令 g[u][0] 为只考虑轻儿子不选择当前结点，g[u][1] 为只考虑轻儿子不选择当前结点。

考虑转移，仍同上，但不考虑重儿子即可。

所以现在的 f 可以表示为

$$f_{u, 0} = \max(f_{v, 0}, f_{v, 1}) + g_{u, 0}$$

$$f_{u, 1} = f_{v, 0} + g_{u, 1}$$

但重链剖分划分区间还是不够的，因为现在还是不能快速一个区间内递推，我们需要一个满足区间结合律的一个东西。

即是下面的广义矩阵乘法，对于 $C = A \times B$，有

$$c_{i, j} = \max\limits_{k = 1}^{k = n}(a_{i, k} + b_{k, j})$$

验证一下，这也是满足结合律的。所以我们可以将递推式改为广义矩阵乘法的形式：

$$
\begin{bmatrix}
f_{u, 0} & f_{u, 1}
\end{bmatrix}
=
\begin{bmatrix}
f_{v, 0} & f_{v, 1}
\end{bmatrix}
\times
\begin{bmatrix}
g_{v, 0} & g_{v, 1} \
g_{v, 0} & -\infty
\end{bmatrix}
$$

其中 $v$ 是 $u$ 的重儿子。所以我们只要在树上维护上述等式最右边的 g 矩阵乘积即可。查询答案即是 1 所在重链最底端（也就是叶子节点）的 f 矩阵乘以树上 1 所在重链的 g 矩阵的乘积即可。发现叶子结点的 f 矩阵也可以表示成

$$
\begin{bmatrix}
0 & a_v \
0 & -\infty
\end{bmatrix}
$$

的形式，所以可以转化为求 1 所在重链所有 g 矩阵的乘积，而答案即是最终矩阵位于 (0, 0) (1, 0) 中较大的位置。

下面考虑修改操作：

一开始的 g 数组很好求出来。

修改不仅会影响本身的 g，还会影响一个点作为轻儿子（或重链的头结点作为轻儿子）递推的 g ，所以为了正确维护 g 矩阵，我们需要不断往上跳，并修改对应点的 g 矩阵（注意到我们递推 g 数组时是用轻儿子的 f 数组递推的，所以为了正确修改，我们应该利用线段树查询所在重链的区间乘积得到原来的 f 数组来正确递推）。根据重链剖分的性质，跳的复杂度为 $O(logn)$，再乘以每次线段树修改的复杂度，即为 $O(log^2n)$。

所以总的复杂度为 $O(mlog^2n)$