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

tzc_wk · 2021-02-01 15:32:55 · 题解

推荐一下自己的博客，喜欢就随手点个关注哦。

难度 *2900 的 hot tea，并且竟然自己想出来了，更新了自己独立想出来的题目的难度上界（bushi）。

我们预处理出 msk_x，其中 msk_x 是一个 22 位二进制数，第 i 位是 1 表示字母表中第 i 个字符在 x 到根节点的路径上出现了奇数次，否则表示出现了偶数次。

显然 x 到 y 的路径上的字符可以重排为一个回文串当且仅当 msk_x\oplus msk_y 在二进制下中至多有 1 位为 1，即 msk_x\oplus msk_y=0,1,2^1,2^2,\dots,2^{21}

考虑使用树上启发式合并，假设我们 dfs 到点 u。显然 u 子树内的路径由 LCA 为点 u 的路径与 LCA 不为 u 的路径两部分组成，后者的最大值为 \max\limits_{v\in son_u}ans_v，关键是如何计算前者的答案，即对于满足 msk_x\oplus msk_y=0,1,2^1,2^2,\dots,2^{21} 且 x,y 在 u 的不同子树中的 x,y，dep_x+dep_y-2\times dep_u 的最大值。由于 2\times dep_u 为定值，故只需求出 dep_x+dep_y 的最大值。

考虑用类似于点分治的处理方式，实时维护一个 mx_x 表示 msk_u=x 的 u 中 dep_u 的最大值。依次 dfs u 的每个子树，先考虑这个子树中每个点的贡献，然后更新 mx 数组。计算贡献的具体方式是，考虑该子树中每一个节点 x，枚举 msk_x\oplus msk_y 的值 v（显然只有 23 种可能），如果 mx_{msk_x\oplus v}\neq 0，就用 mx_{msk_x\oplus v}+dep_x-2\times dep_u 更新 ans_u。这样就能保证我们算出的 x,y 是属于 u 的不同子树了。

还有一点，有人可能会问：这个 mx_x 不是求某个东西的最大值，不满足可撤销性吗。注意，在树上启发式合并中，我们的删除操作是全局删除，需消除子树内所有点的贡献，所以直接把对应的 msk 值赋为 0 就行了，不需要画蛇添足地维护个 std::multiset<int> 之类的。

算下复杂度，dsu on tree 复杂度 1log，枚举 msk_x\oplus msk_y 还有个 23 的常数。总复杂度 23n\log n。不知道有没有更优秀的做法。我一开始还担心能不能跑过去，不过 CF 机子可谓是神一般得快，再加上 3s 时限，跑过去没有大问题。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
template<typename T> void read(T &x){
    x=0;char c=getchar();T neg=1;
    while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    x*=neg;
}
const int MAXN=5e5;
const int MAXV=1<<22;
int n,hd[MAXN+5],to[MAXN+5],id[MAXN+5],nxt[MAXN+5],ec=0;
void adde(int u,int v,int w){to[++ec]=v;id[ec]=w;nxt[ec]=hd[u];hd[u]=ec;}
int msk[MAXN+5],dep[MAXN+5],siz[MAXN+5],wson[MAXN+5];
int mx[MAXV+5],ans[MAXN+5];
void dfs0(int x,int f){
    siz[x]=1;
    for(int e=hd[x];e;e=nxt[e]){
        int y=to[e],z=id[e];if(y==f) continue;
        dep[y]=dep[x]+1;msk[y]=msk[x]^(1<<z);dfs0(y,x);siz[x]+=siz[y];
        if(siz[y]>siz[wson[x]]) wson[x]=y;
    }
}
int pth[MAXN+5],pth_num=0;
void getpth(int x,int f){
    pth[++pth_num]=x;
    for(int e=hd[x];e;e=nxt[e]){
        int y=to[e];if(y==f) continue;getpth(y,x);
    }
}
void add(int x,int f){
    chkmax(mx[msk[x]],dep[x]);
    for(int e=hd[x];e;e=nxt[e]){
        int y=to[e];if(y==f) continue;add(y,x);
    }
}
void del(int x,int f){//全局删除
    mx[msk[x]]=0;
    for(int e=hd[x];e;e=nxt[e]){
        int y=to[e];if(y==f) continue;del(y,x);
    }
}
void dfs(int x,int f){
    for(int e=hd[x];e;e=nxt[e]){
        int y=to[e];if(y==f||y==wson[x]) continue;
        dfs(y,x);chkmax(ans[x],ans[y]);del(y,x);
    } if(wson[x]) dfs(wson[x],x),chkmax(ans[x],ans[wson[x]]);
    for(int i=0;i<22;i++) if(mx[msk[x]^(1<<i)])
        chkmax(ans[x],mx[msk[x]^(1<<i)]-dep[x]);
    if(mx[msk[x]]) chkmax(ans[x],mx[msk[x]]-dep[x]);
    chkmax(mx[msk[x]],dep[x]);
    for(int e=hd[x];e;e=nxt[e]){
        int y=to[e];if(y==f||y==wson[x]) continue;
        pth_num=0;getpth(y,x);
        for(int i=1;i<=pth_num;i++){
            for(int j=0;j<22;j++) if(mx[msk[pth[i]]^(1<<j)])
                chkmax(ans[x],mx[msk[pth[i]]^(1<<j)]+dep[pth[i]]-dep[x]*2);
            if(mx[msk[pth[i]]]) chkmax(ans[x],mx[msk[pth[i]]]+dep[pth[i]]-dep[x]*2);
        } add(y,x);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        char c;int f;cin>>f>>c;
        adde(f,i,c-'a');
    } dfs0(1,0);dfs(1,0);
    for(int i=1;i<=n;i++) printf("%d%c",ans[i],(i==n)?'\n':' ');
    return 0;
}