けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

HL分解

AOJ 2667 Tree

オイラーツアー第4弾!!! でもせっかくなので色んな方法で解いてみたのん!!! Euler ツアー クエリの平方分割 HL 分解 重心分解 (未、todo) 問題へのリンク 問題概要 頂点 0 を根とする頂点数 N の根付き木において以下の Q 個のクエリに答えよ。なお初…

yukicoder 399 動的な領主 (HL分解で通す)

さあ次はいよいよ HL分解の練習をするのん!!!!! 問題へのリンク 問題概要 N 頂点のツリーが与えられて以下の Q 個の操作を行う。初期状態では全頂点の値は 0 である。また最終的に出力する値 res の初期値も 0 とする 2 頂点 u, v 間のパス上に含まれる…

yukicoder 399 動的な領主

ツリー上のクエリの練習 問題へのリンク 問題概要 (意訳) N 頂点のツリーが与えられて以下の Q 個の操作を行う。初期状態では全頂点の値は 0 である。 2 頂点 u, v 間のパス上に含まれる頂点すべて (u, v も含む) の値を +1 する。 Q 回の操作後の各頂点の値…