Do use segment treeだけどHL分解は怖いしやり方がよく分からないのでSegment Treeは使わずLink-Cut Treeを使用。 めちゃ雑に書いたけど想像の10倍ぐらい速かった。いつかSplay木のポテンシャル云々を読んでおこう… 平衡二分木の子が左右入れ替わっても値が…