标签 树形 DP 下的文章

「Codeforces 1153D」Serval and Rooted Tree

题目链接：Codeforces 1153D

Serval 在一棵有根树上玩数字游戏。这棵有根树有 $n$ 个节点，节点 $1$ 是根节点，节点 $i$ 的父亲节点用 $f_i$ 表示。所有非叶子节点上有一个操作 $\max$ 或 $\min$，这意味着这个节点上的值为其所有儿子节点的最大值或最小值。

假设这棵树上有 $k$ 个叶子节点，Serval 会把 $1, 2, \dots, k$ 写在这 $k$ 个节点上（每个数字恰好使用 $1$ 次），并且他想要最大化根节点的值。作为他的好朋友，请你帮他求出根节点的最大值。

数据范围：$2 \le n \le 3 \times 10 ^ 5​$，$1 \le f_i \le i - 1​$。

「Codeforces 70E」Information Reform

题目链接：Codeforces 70E

虽然已经是二十一世纪了，但是大众传媒在海象国并不普及，城市之间只能通过公路交流。海象国中任意两座城市之间有且只有一条路径，且每条道路的长度都是 $1$。

为了进行改革，将会选择一些城市作为信息中心，维护一个信息中心需要 $k$ 元钱。对于其他城市，他们将会从最近的信息中心获得消息，如果设两者直接的距离为 $len$，那么这将花费 $d_{len}$ 元钱。

请你求出一种方案使得花费最小，并求出每个城市会从哪个信息中心获得消息。

数据范围：$1\le n\le 180$，$1\le k\le 10^5$，$0\le d_i\le d_{i+1}\le 10^5$。