If the distance between vertices \(1\) and \(N\) and the number of vertices have different parities, there is clearly no good procedure. Otherwise, it turns out that a good procedure is always constructible. Additionally, if a good procedure is constructible, there is a set of vertices that are visited by the piece in every good procedure, and other than that, there are limited candidates of vertices that needs to be visited.

Let us explain a specific way to construct one. Below, let \(\mathrm{path}(u,v)\) denote the path connecting two vertices \(u\) and \(v\), and \(d(u,v)\) be its length. First, all vertices along \(\mathrm{path}(1, N)\) must always be visited by the piece. Let us cut the edges along \(\mathrm{path}(1,N)\) for now to consider the set of subtrees rooted at the vertices along \(\mathrm{path}(1,N)\), and let \(w_i\) be the size of the subtree rooted at vertex \(i\) (including this vertex).

Here, assume that for a vertex \(s\), the piece does not have to visit the descendant of \(s\). Let us pay attention to the change in the distance between the piece and \(s\). If the operation chooses a vertex in the subtree rooted at \(s\), the piece always approaches \(s\). Otherwise, the piece may go away from \(s\). Therefore, the following must hold:

\(d(1,s)+(N-w_s)\geq d(N,s)+w_s\). ーⒶ

If some vertices violate this, those vertices form a path (Ⓑ: the proof is given later.)

In this case, let \(t\) be the deepest vertex in the path. Let us choose some of the children of \(t\), and let \(W\) be the total size of the subtrees rooted at them. We will consume those \(W\) vertices and the other \(w_t - W\) vertices by first using them to attract the piece to \(t\), and then making pairs. From the assumption, some vertices remain in the subtree rooted at \(t\) when the piece reaches \(t\), but if more vertices remain among the \(W\) than among the \(w_t - W\), they can be consumed in pairs by moving the piece back and forth between \(t\) and the chosen children. This would be impossible if more than half of the remaining vertices are in one of the subtrees rooted at the chosen children, but this is always avoidable since any child of \(t\) satisfies Ⓐ.

Thus, one should choose as few children of \(t\) as possible so that the total size \(W\) of the subtrees rooted at the chosen children satisfies:

\(W\geq (w_t-W)-(d(1,t)+(N-w_t)-d(N,t))\)

\(\iff\) \(2W\geq w_t-(d(1,t)+(N-w_t)-d(N,t))\).

On the other hand, if no vertex violates Ⓐ, one can always construct a procedure where the piece only visits the vertices along \(\mathrm{path}(1,N)\). Let us explain how.

Choose a vertex \(s\) along \(\mathrm{path}(1,N)\). Let \(B_s\) be the sum of \(w_i\) over the vertices \(i\) along the path from \(1\) to \(s\) except \(s\), and \(F_s\) be the sum of \(w_i\) over the vertices \(i\) along the path from \(s\) to \(N\) except \(s\). If none of \(w_s\), \(B_s+d(1,s)\), and \(F_s-d(N,s)\) exceeds half of the sum of them, the vertices in the three groups around the vertex \(s\) can be consumed in pairs to construct a good procedure where the piece only visits the vertices along the path from \(1\) to \(N\).

Furthermore, if no vertex violates Ⓐ, there is always a vertex along \(\mathrm{path}(1,N)\) that satisfies the condition above (Ⓒ: the proof is given later.)

---

■ The proof of Ⓑ

It is clear that the parent of a vertex that violates Ⓐ also violates Ⓐ. Let us assume for contradiction that Ⓐ is violated by two different vertices \(i\) and \(j\) such that none of them is an ancestor of the other.

Here, the following holds for \(i\):

\(d(1,i)-d(N,i)+(N-w_i)<w_i \) \(\iff \) \(d(1,i)-d(N,i)+(N-w_i)+1\leq w_i\).

By using \(d(1,i)-d(N,i)\geq -d(1,N)\), we get:

\((N-w_i)-d(1,N)+1\leq w_i\) (the equality holds only if \(i\) is in the subtree rooted at \(1\)).

Here, \((N-w_i)-d(1,N)\) is at least the total number of vertices that are neither in the subtree rooted at \(w_i\) nor along \(\mathrm{path}(1,N)\). Since \(j\) is not in the subtree rooted at \(i\), the subtree rooted at \(j\) should not overlap with the subtree rooted at \(i\), and we have:

\(w_j\leq (N-w_i)-d(1,N)+1\) (the equality holds only if \(j\) is along \(\mathrm{path}(1,N)\)).

From the above, we have \(w_j\leq w_i\), and the equality holds only if \(i\) is in the subtree rooted at \(1\) and \(j\) is along \(\mathrm{path}(1,N)\).

Therefore, we have \(w_j\leq w_i\) and \(w_i\leq w_j\). To satisfy both equalities, we must have \(i=j=1\), which contradicts the assumption.

---

■ The proof of Ⓒ

Let us gradually move \(s\) from \(1\) along \(\mathrm{path}(1,N)\). From the assumption, \(w_s\) is never the majority.

From the definition, we have \(B_s+d(1,s)=0\) for \(s=1\) and \(F_s-d(N,s) =0\) for \(s=N\). The case one of these \(s\) satisfies the condition may be ignored, so let us assume that \(F_s-d(N,s)\) is the majority for \(s=1\) and \(B_s+d(1,s)\) is the majority for \(s=N\). There is a pair of vertices \(s\) and \(t\) such that \(t\) is one vertex closer to \(N\) than \(s\), and \(F_s-d(N,s)\) is the majority for \(s\), but \(F_t-d(N,t)\) is not the majority for \(t\).

Then, from

\(F_t-d(N,t) = (F_s-w_t)-(d(N,s)-1) = F_s-d(N,s) -w_t+1\) and

\(B_t+d(1,t) = (B_s+w_s)+(d(1,s)+1) = B_s+d(1,s) +w_s+1\),

we have:

\(F_s-d(N,s) > B_s+d(1,s) +w_s\) \(\iff\) \(F_s-d(N,s) -w_t+1+w_t > B_s+d(1,s) +w_s+1\)

\(\iff\) \(F_t-d(N,t)+w_t > B_t+d(1,t)\).

Therefore, \(B_t+d(1,t)\) is not the majority, and from the assumption, neither is \(F_t-d(N,t)\) or \(w_t\), so \(t\) satisfies the condition.