ABC202 E - Count Descendants - かんプリンの学習記録

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${N}$ 頂点の根付き木について以下の ${Q}$ 個のクエリに答えよ．

整数 ${U,D}$ が与えられる．次の条件を満たす頂点 ${u}$ の個数を求めよ．

${u}$ から根への最短パス上に頂点 ${U}$ が存在する．
${u}$ から根への最短パスに含まれる辺の数がちょうど ${D}$ である．

${2\leq N\leq 2×10^5\\ 1\leq Q\leq 2×10^5}$

解説

根から頂点 ${u}$ までの距離を ${d_u}$ とします．求めるものは頂点 ${U}$ を根とする部分木内の ${d_u=D}$ となる頂点の数です．

DFSで訪れた順で頂点を並べてみると，ある部分木の頂点は連続していることがわかります(典型)．よってDFSで頂点を見ていくことにします．現在見た中で ${x=d_u}$ となる頂点 ${u}$ の数を ${C(x)}$ として，これを記録しながらDFSを行います．ある頂点 ${u}$ を訪れた時の ${C(x)}$ の状態と去る時の ${C(x)}$ の状態の差により ${U=u}$ となるクエリの答えが求められます．保持しておく「頂点 ${u}$ を訪れた時の ${C(x)}$ の状態」は ${U=u}$ となるクエリの ${C(x)}$ の値だけでいいので ${O(N+Q)}$ で解けました．