6.10总结 - 洛谷保存站

# [P1040 [NOIP 2003 提高组] 加分二叉树](https://www.luogu.com.cn/problem/P1040)
我们定义:$dp_{i,j}$ 表示选取是下标为区间 $[i,j]$ 的加分最高的二叉树。那么初始的时候 $dp_{i,j} = a_i$ 首先，要中序遍历是 $(1,2,3......n)$ ，然后，我们知道中序遍历是左根右。

那么我们在一串序列 $[i,j]$ 中假设 $k$ 是根，那么左子树就是 $[i,k - 1]$ 右子树就是 $[k + 1,j]$。这个时候只要连边的子树满足条件的时候大的子树也会满足。

因为我们就会先看左子树，左子树满足中序是 $[i,k - 1]$,然后看根 $k$ 最后看右子树 $[k + 1,j]$ 合并后就是区间 $[i,j]$。这也可以证明无后效性且是从小到大转移而来。由此可知转移方程是：

```cpp
dp[i][j] = max(dp[i][j] , max(1ll , dp[i][k - 1]) * max(1ll , dp[k + 1][j]) + dp[k][k]);
```

然后，我们知道当前子树的根就是最大的根，由此我们知道了每个区间中的根是谁。那么我们就可以求出前序遍历。
# [P10391 [蓝桥杯 2024 省 A] 零食采购](https://www.luogu.com.cn/problem/P10391)
求从 $s$ 到 $t$ 的路径，很容易想到最近公共祖先。然后我们可以发现 $c$ 很小。那么我们定义：$f_{i,j}$ 表示从 $i$ 向上走 $2^j$ 步。答案是买的零食的状态。

那么每次的答案不就是从 $i$ 到 $lca(i,j)$ 或 $j$ 到 $lca(i,j)$ 的买的零食的数量吗？那么，最近公共祖先怎么求呢？

我们定义：$dp_{x,i}$ 表示编号是 $x$ 的点向上跳 $2^i$ 步的节点的编号是什么。那么方程应该是什么呢？其实很好求，当前节点跳 $2^{i - 1}$ 时再跳 $2^{i - 1}$ 是不是就等于 $2^i$ 那么我们可以得知方程是:

```cpp
dp[x][i] = dp[dp[x][i - 1]][i - 1];
```

那么接下来就十分好求了，首先你要使他们的深度保持一致。那么就是只要```dep[dp[x][i]] >= dep[y]```。那么我们就让x向上跳 $dp[x][i]$ 个节点。毕竟要它两深度一样也不能不用倍增啊（否则在特殊情况下就我们的倍增形同虚设）。

然后，要注意因为我们每次倍增使看跳了后相不相等，且最后的答案肯定使 $dp_{x,0}$ 因为我们只要中间的距离大于1，我们都是可以跳的。

所以最后我们肯定是输出 $x$ 的父亲，但是，问题出现了。如果在我们将深度变成一致时刚好两个点相等。也就是一个点就是另一个点的祖先。那么我们就会输出错误的答案，所以我们要特判一下这种情况。

然后就是 $f$ 的转移了，其实根 $dp$ 差不多，因为 $f_{i,j}$ 也是等于 $f_{i , j - 1}$ 在跳 $j - 1$ 步得来。只不过这次是或两次的答案。
```cpp
f[u][i] = f[dp[u][i - 1]][i - 1] | f[u][i - 1];
```
然后，求的时候两边的 $f$ 先上跳的时候是不是和倍增求最近公共祖先的时候有点像呢？但是，每次我们都是与原本的答案或一遍。
# [P3501 [POI 2010] ANT-Antisymmetry](https://www.luogu.com.cn/problem/P3501)
我们发现，当 $n$ 是奇数的时候，中间部分取反后会导致答案不一样。所以只有 $n$ 是偶数的时候有答案。

然后，我们发现当两个串是反对称的时候。从对称轴开始的两边也一定是反对称的。那么，这就有了单调性。更长的时候是反对称，那么当长度变小的时候也是。

那么，我们就可以在确定起点的情况下，二分反对称字符串的长度。那么，$check$ 怎么写？我们知道判断两个字符串是反对称，是要把其中一个 $0$ 变 $1$ ，$1$ 变 $0$ 后再反过来。如果直接暴力肯定会超时。那么我们就预处理。

哈希，预处理一个后缀的。记住还要反过来。那么后缀的哈希值就是可以发现是```f[l] - f[r + 1] * dis[r - l + 1]```。然后，只要是小于当前长度的都有一个答案。根据单调性可知。
# [P12382 [蓝桥杯 2023 省 Python B] 树上选点](https://www.luogu.com.cn/problem/P12382)
我们定义：$dp_i$ 表示以 $i$ 为根的最大点权和。我们发现题目要求不能有两个点到根的距离相等，也就是说同一层中只能选一个。且父子节点不能都选。

对于第一个条件，我们就直接每层每层枚举。然后我们就找节点最大值。这个时候就有两种情况。

①最大的是 $i$ 的父节点。

这个时候如果我们选择了 $i$ 那么就不能选择父亲节点。这个时候我们就要在找一个次大值。当然这个次大值我们直接与最大值一起预处理即可。答案就是次大值 $+a_i$。那么当我们选择了 $i$ 的父亲的时候那么答案就是 $dp_{f_i}$

```cpp
if(dp[f[v]] == mx)dp[v] = a[v] + cmx;
```

②最大值不是 $i$ 的父节点

那么我们就可以直接转移。```dp[v] = a[v] + mx; ```

最后找到所有情况的最大值即可。

正在渲染内容...