题解 CF725G Messages on a Tree

标签：CF725G dep 题解 Messages begin Tree

update on 2023.8.9 修正了一些错误。

\(\texttt{link}\)

第 \(i\) 条信息的传输可以表示成 \(x_i\) 走到 \(x_i\) 的某一祖先再走回 \(x_i\) 的路径。所以答案只和 \(x_i\) 的这一祖先有关，记为 \(f_i\)，则 \(ans_i=t_i+2\times dep_{x_i}-2\times dep_{f_i}\)。

若 \(x_i\) 在 \(f_i\) 停下，说明更早的时刻（或同一时刻但编号更小），有 \(x_j\) 经过了 \(f_i\)，且到现在它也没回来。

于是有

\[\begin{cases}(t_i+dep_{x_i}-dep_{f_i},x_i)>(t_j+dep_{x_j}-dep_{f_i},x_j)\\t_i+dep_{x_i}-dep_{f_i}<t_j+dep_{x_j}+dep_{f_i}-2\times dep_{f_j}\end{cases} \]

二元组大小比较以第一项为第一关键字，第二项为第二关键字。

整理得

\[\begin{cases}(t_i+dep_{x_i},x_i)>(t_j+dep_{x_j},x_j)\\t_i+dep_{x_i}<t_j+dep_{x_j}+2\times dep_{f_i}-2\times dep_{f_j}\end{cases} \]

这是个二维偏序，把信息按 \((t_i+dep_{x_i},x_i)\) 排序，依次加入，即可满足第一条关系。

对于第二条关系，我们应该顺着根到 \(x_i\) 的路径向上爬，直到第一个节点 \(u\)，满足 \(t_i+dep_{x_i}<t_j+dep_{x_j}+2\times dep_u-2\times dep_{f_j}\)。所以对于树上每个点 \(u\)，维护 \(g_u\) 表示经过点 \(u\) 的点 \(x_j\) 中，\(t_j+dep_{x_j}-2\times dep_{f_j}\) 的最大值。于是只需找最深度最大的 \(x_i\) 的祖先，满足 \(t_i+dep_{x_i}<g_u+2\times dep_u\)。树剖，维护 \(\max(g_u+2\times dep_u)\)，然后线段树二分即可。算出 \(f_i\) 后更新路径上最大值。

时间复杂度 \(O(n\log^2 n)\)。当然也可以用 LCT 做这种链上问题，可以少一个 \(\log\)。

标签：CF725G,dep,题解,Messages,begin,Tree
From： https://www.cnblogs.com/Terac/p/18038207