第八课

A - 窗口查询

单调队列模板题。

B - 最大矩形

其实这道题的核心思路就是找到从一个点往左右找连续大于等于它的数字。

至于实现就有很多种，单调栈单调队列都能实现，然后笛卡尔树也可以。

另外还有一种被其他人叫做“伪暴力”的做法，实际上就是单调栈罢了。

C - 整数变换

设 $dp[x]$ 表示把 $x$ 变成 $1$ 的最小操作数。那么初始值 $dp[1] = 0$，转移方程为：

$dp[x] = min(dp[x-i], dp[x/k])+1$

很显然 $dp[x-i]$ 的部分是一个区间最小值，可以用单调队列维护，$dp[x/k]$ 特判即可。

D - 最大全0矩阵

可以认为是第二题的拓展。

我们从每一个点向上延升，找到最长连续 $0$ ，这样可以把它看成若干个柱状图，然后就可以用第二题的做法解决。

复杂度 $O(n^2)$。

E - 笛卡尔树

笛卡尔树模板题。

注意题目中说的第 $i$ 个节点是输入顺序，如果排序的话需要额外开个东西记录 $a[i]$ 是第几个输入的。

F - 排列解码

其实放在这一课意义不明（？

设状态 $dp[len][j]$ 满足前 $len$ 个限制且最后一位为 $j$ 的排列数量。

有人可能觉得转移会有大锅实则不然。会发现对于一个排列，我们删去其中一个数，然后把排列中大于它的数全都减一，这样就可以得到一个新的排列。可以继续转移。并且这样转移是不会问题的。

那么接下来考虑转移方程，肯定要根据字符串的限制来分讨的。

$dp[i][j]= \begin{cases} \sum_{k=1}^{j-1} dp[i-1][k] & s[i] =\ 'I' \\ \sum_{k=j}^{i-1} dp[i-1][k] & s[i] =\ 'D'\\ \sum_{k=1}^{i-1} dp[i-1][k] & s[i] =\ '?' \end{cases}$

这里是让已有排列中大于等于 $j$ 的元素加一以保证新状态 $dp[i][j]$ 中的 $j$ 能顺利插入的。

但是看到这个转移方程大家就知道，这样转移的时间复杂度是 $O(n^3)\ $的，需要优化。

每一个求和符号里的内容其实是一样的，所以不难想到用前缀和来快速计算。

那么所以这道题就是前缀和优化 DP 的模板题了。

第九课

A - 树的直径

树的直径模板题，别忘了有两种做法，深搜两遍和一个 DP 做法。

深搜做法大家都会就不说了。

接下来说说 DP 做法。

首先是一个直观的。维护一个 $dp1[u],dp2[u]$ 分别表示 $u$ 节点向下延伸的最长路和次长路，这样经过每一个节点的最长路径就是 $dp1[u]+dp2[u]$，对于每一个节点的答案取最大值即可。这是一个自下而上维护的树形 $dp$ 。

接下来考虑对上面的做法进行优化，因为两个数组的开销有点大。设状态 $dp[u]$ 表示在 $u$ 子树内从 $u$ 出发的最长链长度，那么每次处理出 $u$ 的儿子 $v$ 的 $dp[v]$ 值时，优先计算 $dp[u]+dp[v]+G.wt$ 的大小跟新答案然后再跟新 $dp[u]$ 即可。

B - 树的重心

树的重心模板题，没什么好说的。关于树的重心有如下几个性质：

删除树的重心后，剩余的最大连通分量大小最小。
以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
如果一棵树有多个重心，则至多有两个。
树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
当某节点 $u$ 的最大子树节点 $v$ 的 $size[v]$ 的两倍小于等于 $size[u]$，则该点为以 $u$ 为根的子树的重心。这里会在这个子树有两个重心时取等。

C - 子树重心查询

重心有一个性质，就是最大子树 $2\times size[v] \le size[u]$ 那么这个点就是以 $u$ 为根的子树的重心。这里要用小于等于是为了防止有两个重心的情况。两个重心如果仍然用小于的话就会导致重心被跳过，从而计算出错误的值。

另外还有一个性质就是：把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。

那么如果我们从叶子的方向逐渐往根统计答案，可以认为每一次都在合并两颗子树。

所以我们就可以从重儿子的重心逐渐往父亲方向找，因为重儿子的大小大于整颗子树的一半，所以说新的重心一定在重儿子的重心到父亲的这一条路径上。直接每次往父亲方向找即可。

关于时间复杂度的问题，我们可以想到，重心一定是不断地在向上推进的，所以时间复杂度是 $O(n)$。

D - 路径覆盖统计

树上差分模板题。

E - 树上美丽值

这道题有两种做法。首先来讲一种简单的。

记忆化搜索。我们会发现导致答案不同的三个因素：节点，是否修改，最大公约数。

不妨以他们为中心设立一个 $vis[u][opt][gcd]$ 来保证搜索答案不重不漏。最终所有的答案都记录在 $dp[u]$ 里。

其中 $opt$ 表示是否已经执行了修改操作，如果未执行我们就可以随时执行。

这样设计状态的复杂度其实是 $O(n\log n)$ 级别的。因为对于一串数求最大公约数本来就是越来越小的，这个数量一定是 $log$ 级别的。所以说时间复杂度非常正确。

另外一种做法就是沿着树往下搜的过程去数因子。如果一个点被删掉了，答案就可以认为是桶中出现次数大于等于深度减一的最大因子。因为从根到这个点的距离就是深度，然后这个点变成了 $0$，所以要减一；如果没有删除还有两种可能，一种是都没删，另一种是父亲方向删了一个。由于父亲方向删了一个仍然是出现次数仍然回是 $dep-1$ 所以不用管，都没删再额外数一下即可。

F - 树上行

可以想到 $b$ 只有一种移动方式，一直往根走，然后走到某一个点可以考虑拐弯去别的子树然后一直往叶子走。

那么问题来了 $b$ 为什么不会走到某一个子树然后出来再走别的子树呢？很显然这样是不优秀的。因为树走到头也不可能走到别的子树，如果 $b$ 选择走出来然后再去别的子树就会导致浪费了中间往返的距离。

实现很好写，一直网上走，如果发现网上走碰到了 $a$ 就结束，否则计算一下往别的子树最深可以走到哪里即可。距离也很好算，就是 $a$ 走到该点然后走到最深的距离之和两倍即可。因为只要有距离差 $a$ 一定追不到 $b$，所以 $a$ 跑的距离远，又由于这个游戏是回合制，就导致距离还要乘以二。

没有任何细节。

G - 污染源

首先就像求树的直径一样，求出所有污染节点中最远的两个，分别设其为 $A,B$ 。很显然会有性质：如果一个点到 $A,B$ 的距离都小于等于 $d$ 那么其他污染点到这个点的距离也小于等于 $d$ 。证明很简单，反证易得。

所以问题转化为找到距离最远的两个点距离都小于等于 $d$ 的节点数量。

所以就有了两种做法：

暴力三遍深搜计算答案。
DP 统计答案。

暴力三遍深搜计算答案是非常简单的直接忽略，这边讲一下 DP 做法。

设 $dp[u][0/1]$ 分别表示 $u$ 到其子树内所有污染点的最大距离和次大距离（次大距离需要与最大距离来自不同的子节点子树），$dis[u]$ 表示 $u$ 到其子树外最远污染点的距离。

那么统计也很简单了，就是同时满足 $dp[u][0]\le d$ 且 $dis[u]\le d$ 的点的数量。本质上没有太大区别，就是少了一次深搜。

H - 树上染色

没啥技术含量，直接模拟染色即可。

I - 子树控制

因为父亲方向的节点是固定的，所以可以直接倍增跳到在他控制范围内最远的祖先，然后这一段路上都是可以控制该点的，直接差分即可。

J - 悲伤的树

和上面的一样。题目要求一个点到任意一个祖先的距离都小于等于其点权。那么我们就可以求从这个点往前可以获得的最大权值，这个是非常容易计算出来的，然后如果我们发现了这样一个不合法的节点就要把它删掉，但是每次删除只能删去叶子，所以我们就得把这整棵子树给删去。

同样没有任何细节，记得开 LL 。

K - 非递减路径-树上版本

这道题的做法多得离谱，讲两个比较简单的。这道题首先要注意的应该是路径的概念 $(u,v)$ 和 $(v,u)$ 指的不是同一条路径。

首先还是比较简单的，题目让我们找的有序点对，可以直接把所有 $0$ 边相连的放在一个并查集里，$1$ 边相连的放在一个并查集里。

这时候答案的计算就非常简单，对于每一个 $0$ 边并查集算，然后对于每一个 $1$ 边算，最后就是枚举一个中专点并同时计算与他相连的 $0$ 边并查集中除了它以外的任意点与与他相连的 $1$ 边并查集中除了他以外的任意点相匹配。

这样就可以得出答案了。

另外一个做法是树形 DP。

设状态 $dp[u][0/1]$ 表示从 $x$ 出发重点在其子树内路径合法/路径全为一的方案数。

那么我们从下往上转移的可以得到：

$\begin{aligned} dp[u][1]&=dp[u][1]+dp[v][1]+1\\ dp[u][0]&=dp[u][0]+dp[v][wt]+1 \end{aligned}$

非常好理解，第一行的意思，就是沿着这条边往下有 $dp[v][1]$ 中选择，我也可以只走到 $v$ 点就结束，所以是 $dp[v][1]+1$。第二行也好理解，如果边权为 $0$，那么肯定合法，如果边权为一，往后走也只能为 $1$，所以是 $dp[v][1]$，加一的含义相同。

这里算的是以 $1$ 为根的答案，实际上还可以以任意一个点为根。但是做 $n$ 次 DP 很显然太慢了，因为不管在哪一个点计算方法都是相同的，所以可以考虑换根 DP。用 $ans[u]$ 表示以 $u$ 为根的路径总数，那么很显然有 $ans[1]=dp[1][0]$。

接下来考虑转移，有 $u,v$ 两个点，且 $u$ 是 $v$ 的父亲，我们要求 $v$ 点的答案，要对边权进行分类讨论：

如果 $u,v$ 之间的边权为 $0$，很显然，$u$ 能到的地方 $v$ 也能到，所以 $ans[v]=ans[u]$；
如果 $u,v$ 边权为 $1$；如果终点在 $v$ 的子树内且路径随意，答案即为 $dp[v][0]$，这个和到父亲边权没有关系；接下来从 $v$ 点往外部走，因为到父亲的路径就是 $1$ 了，所以接下来只能走 $1$，我们不妨记录以 $v$ 结束的全 $1$ 链的顶端为 $head_v$，则 $dp[head_v][1]$ 就可以表示所有 $v$ 往上走、拐弯、往下走的全 $1$ 路径。但是往下走的路径已经在 $dp[v][0]$ 中计算了，所以答案为 $ans[v]=dp[v][0]+dp[head_v][1]-dp[v][1]$。

答案就是所有 $ans[u]$ 的总和。