木が線グラフであるときは、複数回既出です。

https://yukicoder.me/problems/no/2859

https://mofecoder.com/contests/mercon2024/tasks/mercon2024_g

(初出は別の問題だと思っています。)

これらは時間と index の二次元座標を 45 度回転させて、segment tree を用いた平面操作をすることで解くことができます。

一般の木の場合でも木を HLD し、各々の線グラフに対して、一点更新と区間 max を平面操作することで解くことができます。

時間計算量は公式解説と変わらない \(O(M \log(N)\log(M\log(N)))\) です。

実装例 c++