Perform the dfs described from the root of tree, and store the order in which nodes are visited into an array.

For any node in the tree, the nodes in its subtree will form a contiguous subarray within the DFS traversal array.

Use Manacher’s algorithm to compute the answer for each node in constant time.