LG CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转好题!重新排序后能变成回文串,出现次数为奇数的字母最多只能有一种因为只有$22$种字符所以我们可以用状态压缩来记录每种字母出现的次数是奇数或者偶数设路径端点的两端为$x,y$,$d_x$表示 1~x 所有状态的异或值,$D_x$表示$x$的深度那么如果这条路径满足条件,则$d_x \oplus d_y$在二进制下最多只有一个$1$它的长度为$D_x + Dy - 2 \times D{lca(x,y)}$我们可以开一个桶来记录每种状态出现的最深的位置是哪里设$sta$为满足条件的状态用每个店更新答案……