1000ms

Difficulty: 6

所属公司 : 科大讯飞

时间 :2025年9月20日

算法与标签>树

会员或题库专享

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

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

会员专享

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

购买题库开通会员

思路与证明

1）核心定义

对每个结点 $u$ 维护两个量：

$down[u]$ ：从 $u$ 向下走，到达其子树内某个红点的最大距离；若子树内不存在红点，设为负无穷（实现时用常数 $-\text{INF}$ 代表，例如 $-10^9$ ）。
$ans[u]$ ：以 $u$ 为根的子树内红点直径的答案。

题目内容

给定一棵以节点 $1$ 为根的树，树上共有 $n$ 个节点，其中某些节点被标记为“红点”。

定义某点 $u$ 的红点直径为：在 $u$ 的子树中，任取两个红点之间的最大距离（路径上经过的边数）。