题解 CF741D 【Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths】

· · 题解

首先一个串能重排形成是回文串当且仅当其字符数量均为偶数或者恰好有一个奇数

实际上对于任意的一条路径我们只关注其任意字符的奇偶性

因为字符只有22种，所以我们可以考虑将其压缩称为一个状态0表示此字符为偶数而1表示为奇

于是对于任意一条路径(u,v)我们考虑其状态就可以通过差分来得到：

不妨记dis_x表示x到1的路径上的字符所形成的状态

于是有：dis_u \oplus dis_v\oplus dis_{lca} \oplus dis_{lca}就是这条路径的状态

注意到异或的性质，所以dis_u\oplus dis_v即这个状态

于是有一条路径合法当且仅当dis_u\oplus dis_v为如下23种状态：

000...00 100...00 ...... 000...10 000...01

接下来我们考虑暴力求解

$2.$我们类似于点分治，对$2^{22}$种不同的状态开个桶 注意到一个点对$u,v$对答案造成的贡献为$dep_u+dep_v-2*dep_{lca}

于是我们考虑从一个点x开始搜索

遍历其所有子树，然后对于一个状态dis_u与其\oplus得到结果合法的状态是固定的23种，于是我们只要检查桶内有没有合法的即可

然后对每个桶都只要维护最大的dep即可

复杂度O(23*n^2)

3.$刚刚的暴力$2$我们采用$dsu$实现就是$O(23*n\log n)$了$qwq 
#include<bits/stdc++.h>
using namespace std;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
int read() {
    char cc = getchar(); int cn = 0, flus = 1;
    while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
    while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
    return cn * flus;
}
const int N = 2000000 + 5 ; 
int n, cnt, idnex, L[N], R[N], head[N], dep[N], sz[N], son[N] ;
int book[N * 10], vis[N], Ans[N], dis[N], Id[N] ; 
struct E {
    int to, next, w ; 
} e[N] ;
void add( int x, int y, int w ) {
    e[++ cnt] = (E){ y, head[x], w }, head[x] = cnt ; 
}
void dfs( int x, int fa ) {
    sz[x] = 1, L[x] = ++ idnex, dep[x] = dep[fa] + 1, Id[idnex] = x ; 
    Next( i, x ) {
        int v = e[i].to ; dis[v] = dis[x] ^ e[i].w, dfs( v, x ), sz[x] += sz[v] ;
        if( sz[son[x]] < sz[v] ) son[x] = v ; 
    } R[x] = idnex ; 
}
void dfs2( int x, int keep ) {
    Next( i, x ) {
        int v = e[i].to ; if( v == son[x] ) continue ; 
        dfs2( v, 0 ), Ans[x] = max( Ans[x], Ans[v] ) ; 
    }
    if( son[x] ) dfs2( son[x], 1 ), Ans[x] = max( Ans[x], Ans[son[x]] ) ; 
    if( book[dis[x]] ) Ans[x] = max( Ans[x], book[dis[x]] - dep[x] ) ; 
    rep( i, 0, 21 ) if( book[dis[x] ^ ( 1 << i )] ) Ans[x] = max( Ans[x], book[dis[x] ^ ( 1 << i )] - dep[x] ) ; 
    book[dis[x]] = max( dep[x] , book[dis[x]] ) ;
    Next( i, x ) {
        int v = e[i].to ; if( v == son[x] ) continue ; 
        rep( j, L[v], R[v] ) {
            int u = Id[j] ; 
            if( book[dis[u]] ) Ans[x] = max( Ans[x], book[dis[u]] + dep[u] - 2 * dep[x] ) ; 
            rep( k, 0, 21 ) if( book[dis[u] ^ ( 1 << k )] ) Ans[x] = max( Ans[x], book[dis[u] ^ ( 1 << k )] + dep[u] - 2 * dep[x] ) ; 
        }
        rep( j, L[v], R[v] ) book[dis[Id[j]]] = max( book[dis[Id[j]]], dep[Id[j]] ) ; 
    }
    if( !keep ) rep( i, L[x], R[x] ) book[dis[Id[i]]] = 0 ; 
}
signed main()
{
    n = read() ; int x; char ch ; 
    rep( i, 2, n ) {
        scanf("%d", &x), cin >> ch, add( x, i, 1ll << ( ch - 'a' ) ) ; 
    }
    dfs( 1, 1 ), dfs2( 1, 1 ) ;
    rep( i, 1, n ) printf("%d ", Ans[i] ) ;
    return 0;
}