1000ms

Difficulty: 7

所属公司 : 科大讯飞

时间 :2024年8月3日

算法与标签>动态规划

会员或题库专享

请先，开通会员或购买题库科大讯飞机考编程题库，可解锁完整内容。

购买科大讯飞机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（科大讯飞机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

以站点 $1$ 为根做树形动态规划。一条合法链可以看成以某个站点 $u$ 为“最高点”（链上最靠近根的点），再向两侧各延伸一条子链，并且两侧使用同一种比较方向。

对每个站点 $u$ 维护两组量：

$f[u][0]$ 、 $g[u][0]$ ：在“子节点库存 $\ge$ 当前站点”这一方向上，从 $u$ 向下的最长子链长度与次长子链长度；
$f[u][1]$ 、 $g[u][1]$ ：在“子节点库存 $\le$ 当前站点”这一方向上的最长与次长。

题目内容

一座补给站网络由 $n$ 个站点与 $n-1$ 条通道组成，整体构成一棵树。站点编号为 $1$ 到 $n$ ，其中站点 $1$ 为根。第 $i$ 个站点的库存为 $a_i$ 。记站点 $i$ 的父节点为 $fa_i$ ，并规定 $fa_1=1$ 。

现在要在这棵树上找一条最长的简单链，使链上涉及的站点满足以下两种条件之一：

对链上的相关站点，均满足 $a_{fa_i} \le a_i$ ；
对链上的相关站点，均满足 $a_{fa_i} \ge a_i$ 。