Transform the given tree into a rooted tree with an arbitrary root, and consider the following DP (Dynamic Programming).

• \(\text{dp}[i][j][k]:=(\)The number of choices of vertices out of the vertices of the subtree rooted at \(i\), such that when takahashi are placed at each of those vertices, there are exactly \(j\) vertices guarded by takahashi, where
  • \(k = 0\) means that a takahashi is placed at Vertex \(i\),
  • \(k = 1\) means that no takahashi is placed at Vertex \(i\), and Vertex \(i\) is not guarded by any takahashi, and
  • \(k = 2\) means that no takahashi is placed at Vertex \(i\), and Vertex \(i\) is guarded by one or more takahashi.\()\)

The DP above naively requires \(O(N^2)\) computations when merging the DPs of subtrees. Since we need to merge them \(N-1\) times, the total computations are \(O(N^3)\), which does not fit in the time limit. However, for the DP of a subtree with \(X\) vertices, we can ignore \(j\) such that \(X \lt j\). Therefore, we can reduce to at most \(O(XY)\) the time required to merge the subtree with \(X\) vertices and the subtree with \(Y\) subtrees.

At a glance it may just seem improving the constant factor, but actually the total computation complexity of \(N-1\) merges has essentially been improved; specifically, it is \(O(N^2)\).

For example, the following precise analysis on complexity is possible:

Prepare an undirected graph \(G\) of \(N\) vertices and \(0\) edges, where Vertex \(i\) on the tree corresponds to the Vertex \(i\) in \(G\).

When merging a subtree \(A\) of \(X\) vertices and a subtree \(B\) of \(Y\) vertices, add an undirected edge from every vertex in \(A\) to every vertex in \(B\). The number of edges added is \(O(XY)\), the computational cost required to merge.

After all merges complete, \(G\) is a complete graph with \(O(N^2)\) number of edges, which is equal to the total sum of computational complexity required for all merge in the DP on tree described above .

Sample code (Python)

Alternatively, one can hold the following two states independently as indices of DP:

• whether or not a takahashi is placed on Vertex \(i\), and
• whether or not Vertex \(i\) is guarded by one or more takahashi.

Sample code (C++)