以下、

• グラフの頂点は0-indexed
• グラフを0を根とした根付き木とみなす

とします。

解答

ここで、 以下のように多項式を定めます。

• \(dpA_v(x)\)：\(x^k\)の係数が「\(v\)を根とした部分木だけ見たとき、高橋くんが警護されている頂点がちょうど\(k\)個となって、かつ頂点\(v\)に 高橋くんがいる ような配置の場合の数」となるような多項式
• \(dpB_v(x)\)：\(x^k\)の係数が「\(v\)を根とした部分木だけ見たとき、高橋くんが警護されている頂点がちょうど\(k\)個となって、かつ頂点\(v\)に 高橋くんがいないけど誰かに警護されている ような配置の場合の数」となるような多項式
• \(dpC_v(x)\)：\(x^k\)の係数が「\(v\)を根とした部分木だけ見たとき、高橋くんが警護されている頂点がちょうど\(k\)個となって、かつ頂点\(v\)は 高橋くんがいない上に警護されてない ような配置の場合の数」となるような多項式

遷移の式は以下のように定められます。ただし\(ch(v)\)は\(v\)の子供（\(v\)と辺で繋がっているもののうち、\(v\)と\(0\)のパス上に無いような頂点）全体の集合とします。

\[dpA_v(x)=x\prod_{u\in ch(v)}(dpA_u(x)+dpB_u(x)+xdpC_u(x))\]

\[dpB_v(x)=x\left(\prod_{u\in ch(v)}(dpA_u(x)+dpB_u(x)+dpC_u(x))\right)-x\left(\prod_{u\in ch(v)}(dpB_u(x)+dpC_u(x))\right)\]

\[dpC_v(x)=\prod_{u \in ch(v)}(dpB_u(x)+dpC_u(x))\]

また、空集合における\(\prod\)は1を返すものとします。 このとき、

\[dpA_0(x)+dpB_0(x)+dpC_0(x)\]

が答えとなります。

計算量

頂点\(v\)の子が\(u_1,\ldots,u_k\)として,部分木のサイズが\(a_1,\ldots,a_k\) である場合を考えます。 このとき、1番目から順番にマージしていくことを考えます。ここで、\(n\)次多項式と\(m\)次多項式のマージは\(O(nm)\)でできることに気をつけると、 \(a_1a_2+(a_1+a_2)a_3+(a_1+a_2+a_3)a_4+\cdots +(a_1+\cdots +a_{n-1})a_n \) \(=\sum_{i<j}a_ia_j\)

これは対称式であるため、どのように計算しても同じ値になります。

これは整理すると \(\frac{1}{2}\left((a_1+\cdots+a_n)^2-(a_1^2+\cdots +a_n^2)\right)\) となります。よって最終的に全体の計算量は

\(\frac{1}{2}\sum_{v \in V}\left(size(v)^2-\sum_{u\in ch(v)}size(u)^2\right)\)

\(=\frac{1}{2}\sum_{v\in V}size(v)^2-\frac{1}{2}\sum_{u\in V\setminus\{0\}}size(u)^2\)

\(=\frac{1}{2}size(0)^2\)

\(=\frac{1}{2}N^2\)

よって全体の計算量は\(O(N^2)\)となります。

注：\(size(v)\)は\(v\)を根としたときの部分木のサイズ

余談

多項式の積自体は愚直に計算しても十分間に合います。 また、高速フーリエ変換による畳込みを使うと多項式の積がより高速に計算することができます。 この問題は\(\mod 10^9+7\)なので畳み込みの計算が（できなくはないけど）大変なのですが、もし\(\mod 998244353\)ならばACLのconvolution等で多項式の積が簡単に計算できます。

このとき、\(n\)次式と\(m\)次式をマージする場合の計算量は\(O((n+m)\log{(n+m)})\)となります。

また、畳み込みを使う場合には以下の方法が役立ちます。

複数の多項式の積を計算する際、次数の低いものから順番に掛けると実行時間が短くなります。つまり、

1. 多項式の集合\(f_1(x),\ldots,f_n(x)\)を用意する。
2. 集合のサイズが1になるまで以下の操作を繰り返す
3. 集合の要素を次数が小さい順に並べた時に先頭2つの要素を取り出して集合から削除する.取り出した多項式を\(p_1(x),p_2(x)\)とする.
4. \(p_1(x)\)と\(p_2(x)\)の積を計算して,計算結果を集合に入れる

これを繰り返すと,最終的にもとの集合は \(f_1(x)\times \cdots \times f_n(x)\) からなる一点集合となります。

ソートがボトルネックに見えますが、（多項式の次数,多項式）のペアを優先度付きキューに入れて管理することで計算時間が高速になります。