パスグラフは（問題文同様）長さを頂点数で表すことにします。（一般的に辺の数とする事が多いので注意してください）

\(x = 1\) のときは長さ \(3\) のパスです。これは、頂点数が \(3\) 以上の木には常に含まれます。よって以下では \(x \ge 2\) のみ考えます。

ある木 \(T\) に「長さ \(x\) のムカデグラフが含まれる」ことと「長さ \(x\) のパスグラフであって、次数列 \(d \ge (3, 4, \dots ,4, 3)\) となるものが存在する」ことは同値です。よって、これが含まれるかどうかを考えます。

解法 1

木 DP をします。頂点 \(v\) について

• \(dp[v] =\) \(v\) を終点とする \(v\) の部分木内のパスであって、次数列 \(d \ge (3, 4, \dots)\) を満たすようなパスの長さの最大値

を管理します。

この値は葉から順に更新することができます。具体的には、

• \(\text{deg}[v] \ge 4\) のとき

  自分を始点とすること、および子からつなげることができます。

  よって \(\displaystyle dp[v] = \max \left( \max_{u \in \text{ch}[v]}(dp[u]) + 1, 1 \right)\) です。

• \(\text{deg}[v] = 3\) のとき

  自分を始点とすることのみできます。よって \(dp[v] = 1\) です。

• \(\text{deg}[v] \le 2\) のとき

  \(dp[v] = 0\) です。

答えは DP で管理している値を利用して、各頂点 \(v\) について

• 頂点 \(v\) がパスの端点となる場合
• 頂点 \(v\) がパスの折り返し地点となる場合

それぞれについて最大値をもとめて、答えを更新すればよいです。計算量は \(O(N)\) です。

実装例 (PyPy) （この実装例では簡単のために \(O(N \log N)\) となっています）

解法 2

葉の次数が \(3\) 以上かつ葉でない頂点の次数が \(4\) 以上の木を「よい木」と呼ぶことにします。よい木における「長さ \(x\) のムカデグラフ」の \(x\) の最大値は、木の直径と一致します。

よって、元の木に部分グラフとして含まれるような、すべての「極大なよい木」を考えればよいです。

次数 \(4\) 以上は高々 \(1\) 回、次数 \(3\) の頂点は高々 \(3\) 回しか極大なよい木に出現しないため、極大なよい木の合計頂点数は \(O(N)\) で抑えられます。よって、そのすべてについて直径を求めれば、計算量は \(O(N)\) です。