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