数据结构 2021 小作业3 Hint

[Sakits]

数据结构 2021 小作业3 Hint

  由于数据结构答疑组比较佛系再加上觉得太早发 hint 不太合适所以发得比较晚...但是这样可能对卡题的同学没有什么帮助，所以下次应该会稍微早一点发，抱歉没能帮到卡题的同学qaq

1109. 扩展二叉树

  通过前序遍历用 dfs 把树建出来搜中序和后序遍历即可。

  PS ：前 中 后指的是根的相对位置，前序：根左右，中序：左根右，后序：左右根。

1112. 分割树

  其实题设中的分割点就是树的重心的定义。

  树的重心的性质：

    1. 重心其所有子树的大小都不超过 $\frac{n}{2}$。

    2. 树中所有点到某个点的距离和中，到树的重心的距离和是最小的，最多有两个重心，如果有两个重心，那么到它们的距离和相同。

    3. 把两棵树通过两个点相连得到一棵新的树，新的树的重心必定在连接两棵树的重心的路径上。

    4. 一棵树添加或删除一个节点，树的重心最多会移动一条边的位置。

  利用性质 1 和性质 2 都可以以 $O(n)$ 的时间复杂度找到树的重心。

1113. travel

  树的任何一个子树在前后序遍历中都是连续的一个区间，设 $\text{solve}(l_1, r_2, l_2, r_2)$ 表示一个子树里的方案数，这个子树在前序遍历里的区间是 $[l_1, r_1]$，后序遍历里的区间是 $[l_2, r_2]$，把下一层的所有子树区间给找出来，递归求解，回溯的时候把 $C(m,$ 子树个数$)$ 的组合数乘上去就可以了。

1114. String

  小写字母只有 26 个，线段树维护每个区间里每种字母的个数，每次用类似桶排的方法排序即可。

1115. Interesting Knapsack

  树形依赖背包。

  可以按 dfs 序 DP ，设 $f_{i, j}$ 为 dfs 序为 $i$ 的点，已经选了重量为 $j$ 的最大价值，$next_i$ 为 $i$ 的下一个子树的 dfs 序，则有转移：
$$
f_{i, j} \rightarrow f_{next_i, j}
$$
$$
f_{i, j} + w_i \rightarrow f_{i + 1, j + v_i}
$$

1116. Forest

  有一个结论：两棵树合并之后的直径的端点一定是这两棵树合并前的直径的四个端点中的两个。

  把断边倒过来当作加边做即可。

1117. Query on a path

  如果没有二类边，那么两个点 $a, b\ (a < b)$ 的距离就是 $sum_b - sum_a$。

  如果通过一条长为 $z$ 的二类边 $c \rightarrow d$，那么 $a, b$ 的距离就是：
$$
a \rightarrow c \rightarrow d \rightarrow b
$$
$$
= (sum_c - sum_a) + z + (sum_b - sum_d)
$$
$$
= (sum_b - sum_a) + (sum_c - sum_d + z)
$$
  当 $a < c$ 且 $d < b$ 时一条二类边才可以被经过，相当于一个二维数点，一维排序一维树状数组即可。