適当に根を取り根付き木として、木 dp により計算を行います。

木の部分グラフがまた木となるためには頂点集合を決定することにより辺集合は（高々）一意に定まることに注意してください。以下、木となる部分グラフと（辺を適切に決定することで木をなすような）頂点集合を適切に同一視します。

以下の条件を満たす（頂点数が \(0\) でない）グラフを 広義アルカン と定義します。

• グラフは無向木である
• すべての頂点の次数が \(1\) または \(4\) である

すなわち、アルカンから次数 \(4\) の必要性を外したものを広義アルカンとしています。グラフがアルカンであることと頂点数が \(5\) 以上の広義アルカンであることは同値であるため、広義アルカンについて頂点数の最大値が求められればよいです。

根でない頂点 \(v\) に対し、\(dp_v\) を（\(v\) を含む）\(v\) の子孫のみを用いる部分木であって、\(v\) の親を追加することで広義アルカンになるようなものの頂点数の最大値として定義します。

dp の計算を行います。

（\(v\) を除く）\(v\) の子孫について計算が行われているとして \(dp_v\) の値を計算します。

\(v\) の次数は \(1\) または \(4\) となるため場合分けを行います。

\(v\) の次数が \(1\) のとき、\(v\) に隣接する頂点は \(v\) の親のみであるため頂点数は \(1\) となります。

\(v\) の次数が \(4\) のとき、\(v\) に隣接する頂点は \(v\) の親および \(v\) の \(3\) つの子であるため、\(v\) は子を \(3\) つ以上持つ必要があります。逆に子を \(3\) つ以上持つとき、子 \(u_1, u_2, u_3\) についてその親となる \(v\) を追加することで広義アルカンとなるグラフのうち頂点が最大であるものの頂点集合と \(v\) を用いることで \(dp_{u_1} + dp_{u_2} + dp_{u_3} + 1\) 頂点で条件を満たすものが取れます。この最大値については、単に \(v\) の子 \(u\)であって \(dp_u\) の値が大きいもの \(3\) つを取ればよいです。

以上の結果を用いて答えの計算を行います。

部分グラフが広義アルカンであるとき、最も深さが小さい頂点は一意に定まります。この頂点を \(v\) とおき、\(v\) の次数により場合分けを行います。

\(v\) の次数が \(1\) のとき、\(v\) に隣接する頂点を \(u\) とすると、頂点数の最大値は \(dp_u + 1\) となります。

\(v\) の次数が \(4\) のとき、\(v\) に隣接する頂点を \(u_1, u_2, u_3, u_4\) とすると頂点数の最大値は \(dp_{u_1} + dp_{u_2} + dp_{u_3} + dp_{u_4} + 1\) となります。\(v\) が子を \(4\) つ以上持つ必要があることに注意してください。

この計算を各 \(v\) について行うことで答えを求めることができます。時間計算量は全体として \(O(N)\) です。