因为 $v$ 已经是黄色，我们只需要找一个红色点和一个绿色点在 $v$ 的不同子树，并且距离最短。也就是只需要找到和 $v$ 距离最近的两个在不同子树的红色点和绿色点。$v$ 子树内的情况只需要用线段树维护 DFS 区间的最小深度。$v$ 子树外的情况可以用点分树维护（官方题解做法）或者树上动态 DP，使用树链剖分或者 LCT，时间复杂度 $O((n+q)\log^2n)$ 或者 $O((n+q)\log n)$。
QOJ.ac
QOJ
Discussion #1218 for Problem #17167. Traffic Lights
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2026-03-06 01:30:31
Last updated: 2026-03-06 01:30:37
题解
Comments
No comments yet.