CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
给定一颗以 \(1\) 为根的树每个节点上有一个 \(a\sim v\) 的小写字母，求每个子树内最长的链的长度，使得链上的字母通过重排成为回文串。 \(n\leq 10^5\) 。
DUS on tree 复健题 。首先考虑到回文串的性质：只有 \(1\) 个或没有出现奇数次的字符，再加上这一题的小写字母只有 \(22\) 个，可以状压一下。然后处理出每个点到根的状压距离 \(dis_i\) （哪些字符有奇数个），然后就有一个朴素的 \(n^2\) 枚举做法（实现不好退化成 \(O(n^3)\) ）：因为 \(dis_i\oplus dis_j\) 会将 \(lca(i,j)\) 以上的点全部去掉，所以剩下的部分就是链上的答案。
然后考虑优化算法：先 dfs 一次得出树上每个节点的重儿子，然后维护一个桶：
\[f_i=\max\limits_{dis_j=i\&\&j\in subtree(root)}\{dep_j\} \]然后先递归求出其他儿子的答案，并清空桶。在求重儿子时不清空桶，直接合并轻儿子的答案。求答案的时候只用搜 \(f_{dis_{j}\oplus (2^k)}\) ，然后最后就取 \(\max\) 即可。
标签：paths,Dokhtar,kosh,Mehrdad,tree,marked,dis,CF741D From： https://www.cnblogs.com/zhouzizhe/p/16824336.html