CF914E 题解
题面有点不清晰，翻译一下。
给定一棵树，每个点上面有一个字母。定义一条简单路径回文，当且仅当路径上的字母任意排列后可能成为回文串。对于每个节点，求经过它的回文路径数量。一个点也构成一条回文路径。
容易想到，路径上字母出现次数全为偶数时满足条件，有一种字母为奇数时也满足。树上路径统计，考虑点分治。
对于一个分治中心 \(u\)，分 \(4\) 种情况讨论。
-
路径两端位于 \(u\) 的不同子树内，开桶统计。
-
路径两端位于 \(u\) 的同一子树内，递归处理，不关 \(u\) 的事。
-
路径一端就是 \(u\)，这个单独处理，遍历分治树统计。
-
路径就只有一个点 \(u\)。最后加一即可。
以下 \(u\) 表示当前分治中心。
\(Dist_i\) 表示 \(u\) 到 \(i\) 的路径异或和，可以深搜得出。
\(Count_x\) 作为桶，统计分治树中 \(Dist\) 为 \(x\) 的节点数。不含 \(u\)。
首先处理 \(Dist\) 和 \(Count\)。
对于 \(u\) 的每棵子树，先遍历一下，将子树中的 \(Dist\) 从 \(Count\) 里减掉，防止重复，避免了容斥（当然容斥会快一些，但是有点麻烦），然后统计答案。
最后将子树 \(Dist\) 加回 \(Count\) 里。
维护路径加，离线单点查询，考虑差分。这里求 \(lca\) 用的树剖，倍增常数大且疑似被卡，第 81 个点会超时。
时间复杂度 \(O(C\cdot n\log^2n)\)，其中 \(C = 20\)，字母个数。常数较小，可过，跑了两秒（
空间 \(O(2^C+n)\)。
考虑优化，\(lca\) 带来了一个 \(\log\)。可以在每次点分时，维护以 \(u\) 而不是 \(1\) 为根的差分数组，并在点分完成时直接将这次的变动加到另一个 \(ans\) 数组中，具体见 Daniel_lele 大佬的题解。可以 \(O(C\cdot n\log n)\) 解决。%%%