LC 2791. 树中可以形成回文的路径数
https://leetcode.cn/problems/count-paths-that-can-form-a-palindrome-in-a-tree/
这题现在想起来不是很难，感觉对于这类树状的图形使用DFS似乎是唯一的选择，尤其是对于这些n>=10^5的case.
我第一次写法会在每个节点上，逐个比较每个孩子可以产生的匹配，但是这样容易产生特别高的时间复杂度，或者是不太容易控制的时间复杂度。 https://leetcode.cn/problems/count-paths-that-can-form-a-palindrome-in-a-tree/submissions/452163269/
class Solution:
def countPalindromePaths(self, parent: List[int], s: str) -> int:
n = len(parent)
child = [[] for _ in range(n)]
for i in range(1, n):
p = parent[i]
child[p].append(i)
cnt = Counter([0])
def search(root, now):
ans = 0
for c in child[root]:
bit = (1 << (ord(s[c]) - ord('a')))
x = now ^ bit
ans += cnt[x]
for i in range(26):
ans += cnt[x ^ (1 << i)]
cnt[x] += 1
ans += search(c, x)
return ans
ans = search(0, 0)
return ans