前言
离上一篇博客的时间算来已经有3个月了，趁着现在期末周结束的闲暇时光总结一下本学期数据结构的小作业，以及涉及到的算法。
以及不得不说，PPCA真的很累。
P1113 Travel
题意
给定 M 叉树的前序遍历和后序遍历，求树可能的形态总数。
解法
我们知道给定前序遍历（或者后序遍历）+ 中序遍历可以确定一棵二叉树，而前序和后序不能。原因在于前序遍历是：根 左 右，后序遍历是：左 右 根，我们发现它们对于左右儿子是不做区分的。因此给定前序和后序只能确定父子关系。
知道这件事后这道题就很好解决：只要把父子关系都确定出来，再统计可能的排列数就好。
P1114 String
题意
维护一个小写字母组成的字符串，有 $M$ 次操作，每次将一段区间按升序或降序排列。最后输出操作后的字符串。$M \le 1e6$
解法
考虑字符集如果只有0和1，每次排列实际上就是将一段赋值为0，另一段赋值为1。因此我们考虑维护一棵 “赋值线段树”。对于此题，由于字符集不大，因此维护27棵线段树即可解决问题。
具体来讲，对于一个操作，按字母顺序以及这个区间内的字母个数（这是可以区间查询的）一段段赋值。
P1115 Interesting Knapsack
题意
确实很 Interestring，而且也很经典。
树形背包问题。$N$ 个物品，每个物品有价值 $v_i$ 以及重量 $w_i$，以及可能有一个依赖关系，即购买第 $j$ 件物品前必须先购买第 $i$ 件物品。保证依赖关系为拓扑图。$N \le 5000$
解法
常规的树形背包复杂度是 $O(N^3)$ 的，转移方程考虑树形 DP 的经典设计，$f[u][i]$ 表示在 u 的子树（包括自己）中已使用空间为 i 的最优价值（即对树上每个节点做一次背包，假设每个节点容量都是 1）
对于一个子树节点，需要枚举两层循环。
而这题数据范围是 $O(N^2)$ 的，我们考虑复杂度的瓶颈：我们枚举了要选择的节点个数，而实际上子树我们也枚举过一遍，这里面重复做了事情。
因此我们考虑使用前面已经搜过的信息，考虑按 dfs 序转移。设 $f[i][j]$ 表示 dp 到 dfs 序为 i 的节点，已经选了 j 个节点，则选 or 不选转移如下
P1116 Forest
题意
一棵树不断删边，每删一次边询问一次所有树直径的乘积。$N \le 10^5$
解法
有点难，看了题解才会。首先遇到这种不断维护的问题都可以想想能否离线，这题就可以倒着做（也是一种离线）
考虑树的合并，有一个结论：新树的直径两端点一定在原树直径两端点中。
P1117 Query on a path
题意
一条链上连有另外 $M$ 条边，规定至多经过一次这种边，$Q$ 次询问求途中两点最短路。（都有权值）
解法
先将链上的边权记前缀和，则只走第一类边代价就是 $sum[v] - sum[u]$，考虑走第二类边 $a, b, w$，代价就是 $sum[a]-sum[u]+sum[v]-sum[b]+w$，也就是说只要最小化 $sum[a]-sum[b]+w$
于是问题抽象为有若干个带权区间，每次询问落在固定区间内的最小值。二维约束问题按惯例仍然是一维排序一维树状数组。
P1129 拉丁舞配对课
题意
n 名同学排成一排，每个同学都有一个拉丁舞水平值和一个性别。每次都会请一堆相邻的、水平差最小的异性出列，出列后两边往中间靠拢，即 ABCD ，BC 出列后变成 AD，AD 相邻。
解法
用堆模拟即可。
P1130 删除数字
题意
定义这样一个集合：
- 1 是集合元素。
- 若 P 是集合元素，则 2P+1、4P+5 也是集合元素。
现在将这个集合的前 k 个数字并成一个数字串 （e.g. 137915…），然后删除数字串中 m 个位置的数字，使得剩下的数最大，问删除后的数字是多少。
解法
集合的定义是幌子，只要确信数字串长度不会太大就好了，考虑删除数字。
1379… 如果当前数字的后一个数字比自己大，那么删掉当前数字一定更优，因此一直这样直到用完 m 次机会即可。
P1131 加分二叉树
题意
对于一个每个点有权值 $d[i]$ 的二叉树，定义子树 u 的分数为：
且规定只有一边子树，另一侧空树的分数算作 1；叶子节点，分数即为 $d[i]$
试求一个中序遍历为 1, 2, 3, … n 且根节点分数最高的二叉树。
解法
中序遍历可以看作是投影，对于一个既定的中序遍历，我们可以选择其中任意一个位置 pos 作为根节点，那么左子树中序遍历就是 $[l, pos-1]$，右子树就是 $[pos+1, r]$，我们记 $f[l][r]$ 为加分值，那么
P1133 二哥吃糖
题意
初始状态所有盒子里都有一颗糖，有三种类型的操作：
- 合并两个盒子
- 吃掉一个盒子里的所有糖
- 询问当前糖果数第 P 多的盒子有多少糖， $1 \le P \le 10$
解法
并查集，删除打标记。P 范围这么小的话直接用堆就可以，再大可以考虑用平衡树维护。