概要
解法
治療した歯を数え上げましょう。
つまり、「部分根付き木の集合 $\mathcal{T}$が。$T\in \mathcal{T}$ の和集合の頂点数を求めよ。」というタイプの問題です。
$2$ つの部分根付き木 $T_1, T_2$ の関係は、
- $T_1\cap T_2 = \emptyset$
- $T_1\subset T_2$ または $T_2\subset T_1$
のいずれかです。よって、複雑な包除原理の類は必要ありません。まず、ある $T’\in \mathcal{T} (T’\neq T)$ に対して $T\subset T’$ となるような $T$ は、和集合の計算から除外してしまって構いません。除外後に残る部分根付き木の集合は、どの $2$ つも交わらないため、和集合の要素数は各々の要素数の和として計算できます。
結局、以下のようにして計算することができます。
- 治療済の歯の数を計算する。（最後に全体から引く）
- 各部分根付き木 $(p_i,q_i)$ が他の部分根付き木 $(p_j,q_j)$ に含まれるになっているかどうかを確認する。$(p_i,q_i)$ を含む根付き木は、その先祖を根とするものしかありえないので、根付き木全体の集合を管理して $O(N)$ 通り調べることで判定できる。
- 他の部分根付き木に含まれないような部分木に対して、その頂点数を足していく。これは、深さ $p$ から計算できる。
