Readme

2791.Count-Paths-That-Can-Form-a-Palindrome-in-a-Tree

首先注意题意，路径上的字符可以"rearranged"。并不是说路径本身是回文串。

对于回文串，我们不关心每个字符出现的具体频次，而是只关心频次的奇偶性。所以任何路径其实可以用一个长度为26位的01串编码来表示，通过这个01串我们就可以判断是否是回文（奇数频次的字符不能超过1个）。

接下来考虑我们如何能遍历任意两点之间的路径的编码呢？一种常见的遍历方法是对于任意一个节点，想象它是路径的拐点，在它的子节点里寻找路径的左半部分和右半部分。但是这个想法在这里行不通，我们无法穷举所有子节点的01串。

本题的关键点在于，任意两点u,v之间路径的01串编码，等于u到根节点r的01串编码，再加上v到根节点r的01串编码。中间会有一段重复两遍（即uv的LCA和Root这段），但是算上它们并不影响u,v之间路径编码里每一位的奇偶性。所以我们其实只需要记录所有节点到根节点的路径的01编码即可。

本题的具体做法只需要简单的DFS。对于任何u到r的01编码state，我们用hash表查找是否已经存在其他节点v到r的01编码state2：

1. 如果state2==state，那么uv的路径上就所有的字符频次都是偶数，是回文串。
2. 如果state2和state只差别1个bit，那么uv的路径上就有一个字符的频次是奇数，也是回文串。