We define the length of a path graph by the number of vertices (as in the problem statement). (Note that it is commonly defined as the number of edges.)

For \(x = 1\), a centipede graph is a length-\(3\) path, which is always contained in a tree with three or more vertices. Thus, we only consider \(x \ge 2\).

A tree \(T\) contains a length-\(x\) centipede graph if and only if it contains a length-\(x\) path graph with degrees \(d \ge (3, 4, \dots ,4, 3)\), so we will consider if it contains such a graph.

Solution 1

We perform a tree DP (Dynamic Programming). For a vertex \(v\), we manage

• \(dp[v] =\) the maximum length of a path ending at \(v\) within the subtree rooted at \(v\), with degrees \(d \ge (3, 4, \dots)\).

This can be computed from the leaves. Specifically,

• If \(\text{deg}[v] \ge 4\):

  We may let the current vertex be the starting vertex, or let the path extend from a child.

  Thus, \(\displaystyle dp[v] = \max \left( \max_{u \in \text{ch}[v]}(dp[u]) + 1, 1 \right)\).

• If \(\text{deg}[v] = 3\):

  We may only let the current vertex be the starting vertex, so \(dp[v] = 1\).

• If \(\text{deg}[v] \le 2\):

  We have \(dp[v] = 0\).

The answer can be found based on the values found in DP. For each vertex \(v\), find the maximum value for the following two cases:

• when vertex \(v\) becomes an endpoint of the path;
• when vertex \(v\) becomes a midpoint of the path.

The complexity is \(O(N)\).

Sample code (PyPy) (This implementation costs \(O(N \log N)\) for the sake of simplicity.)

Solution 2

Let us say a tree is “good” when the degrees of the leaves are \(3\) or greater, and the degrees of the non-leaf vertices are \(4\) or greater. The maximum possible \(x\) such that a tree contains a length-\(x\) centipede graph coincides with the diameter of the tree.

Therefore, it is sufficient to consider all “maximal good trees” contained in the original tree as a subgraph.

Since a degree-\(3\) vertices is contained at most three times, and degree-\(4\)-or-more vertices is contained at most once, in a maximal good tree, so the total number of vertices in a maximal good subtree can be bounded by \(O(N)\). Therefore, we can find the diameter for all such trees to find the answer in \(O(N\)) time.