M_sea

CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
CodeForcesLuogu分析吐槽一下这题目名字怎么这么长...显然,如果只有至多一个字符出现次数为奇数,那么...
扫描右侧二维码阅读全文
07
2019/05

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

CodeForces

Luogu

分析

吐槽一下这题目名字怎么这么长...

显然,如果只有至多一个字符出现次数为奇数,那么这条路径就是符合要求的。

字符只有 $22$ 种,可以状压一下,那么只要异或和有至多一个二进制位为 $1$ 就是合法的。

设 $f[i]$ 表示到根路径异或和为 $i$ 的点中最大深度值。

然后上 $\mathrm{dsu\ on\ tree}$ 就好了。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline void chkmax(int& x,int y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

struct Edge { int v,w,nxt; } e[N];
int head[N];

inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

int n;
int dfn[N],id[N],low[N],tim=0;
int dep[N],sz[N],hson[N],xorsum[N];
int ans[N],f[1<<22];

inline void dfs1(int u,int fa) {
    dfn[u]=++tim,id[tim]=u,sz[u]=1,dep[u]=dep[fa]+1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w; if (v==fa) continue;
        xorsum[v]=xorsum[u]^w,dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
    low[u]=tim;
}

inline void dfs2(int u,int keep) {
    //遍历轻儿子
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=hson[u]) dfs2(e[i].v,0),chkmax(ans[u],ans[e[i].v]);
    //遍历重儿子
    if (hson[u]) dfs2(hson[u],1),chkmax(ans[u],ans[hson[u]]);
    //合并
    //单边
    if (f[xorsum[u]]) chkmax(ans[u],f[xorsum[u]]-dep[u]);
    for (re int i=0;i<22;++i)
        if (f[xorsum[u]^(1<<i)]) chkmax(ans[u],f[xorsum[u]^(1<<i)]-dep[u]);
    chkmax(f[xorsum[u]],dep[u]);
    //双边
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==hson[u]) continue;
        for (re int j=dfn[v];j<=low[v];++j) {
            int z=id[j];
            if (f[xorsum[z]]) chkmax(ans[u],f[xorsum[z]]+dep[z]-(dep[u]<<1));
            for (re int k=0;k<22;++k)
                if (f[xorsum[z]^(1<<k)]) chkmax(ans[u],f[xorsum[z]^(1<<k)]+dep[z]-(dep[u]<<1));
        }
        for (re int j=dfn[v];j<=low[v];++j) {
            int z=id[j];
            chkmax(f[xorsum[z]],dep[z]);
        }
    }
    //消除影响
    if (!keep) for (re int i=dfn[u];i<=low[u];++i) f[xorsum[id[i]]]=0;
}

int main() {
    n=read();
    for (re int i=2;i<=n;++i) {
        int f=read(); char c=getchar();
        addEdge(f,i,1<<(c-'a'));
    }
    dep[1]=1,dfs1(1,0),dfs2(1,0);
    for (re int i=1;i<=n;++i) printf("%d ",ans[i]);
    return 0;
}
最后修改:2019 年 06 月 09 日 08 : 58 PM

1 条评论

  1. tiger0132

    Orz

发表评论