Codeforces 741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths（dsu on tree）

时间：2024-06-26 09:35:38

　　感觉dsu on tree一定程度上还是与点分类似的。考虑求出跨过每个点的最长满足要求的路径，再对子树内取max即可。

　　重排后可以变成回文串相当于出现奇数次的字母不超过1个。考虑dsu on tree，容易想到遍历时记录每种情况的最大深度，合并时类似点分的逐个计算贡献再合并即可。这里有个问题是得到某子树信息后，对于原来的根来说，这个信息还要再加上一个偏移量，但直接暴力显然复杂度就不对了。实际上维护信息过程中不断传递偏移量即可。

　　一开始就发现了这个题只开了256M，于是机智的开了个map，悲惨的T掉了。然而题面里深藏不露的说了一句字母范围在a~v。这啥思博题啊。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 500010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,a[N],p[N],fa[N],size[N],deep[N],son[N],len[N],ans[N],t,f[<<];

struct data{int to,nxt;

}edge[N];

void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],len[y]=z,p[x]=t;}

void make(int k)

{

    size[k]=;

    for (int i=p[k];i;i=edge[i].nxt)

    {

        deep[edge[i].to]=deep[k]+;

        make(edge[i].to);

        size[k]+=size[edge[i].to];

        if (size[edge[i].to]>size[son[k]]) son[k]=edge[i].to;

    }

}

inline int rev(int x){return (<<)-^x;}

void update(int k,int x,int op)

{

    if (op==) f[k]=max(f[k],x);

    else f[k]=;

}

void add(int k,int x,int op)//对子树内统计信息时，偏移量为x

{

    update(x,deep[k],op);

    for (int i=p[k];i;i=edge[i].nxt)

    add(edge[i].to,x^(<<len[edge[i].to]),op);

}

int calc(int k,int x)

{

    int ans=f[x]+deep[k];

    for (int i=;i<;i++) ans=max(ans,deep[k]+f[x^(<<i)]);

    if (ans==deep[k]) ans=-N;

    for (int i=p[k];i;i=edge[i].nxt)

    ans=max(ans,calc(edge[i].to,x^(<<len[edge[i].to])));

    return ans;

}

int dfs(int k)//获得的该子树信息的偏移量

{

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=son[k])

    {

        int delta=dfs(edge[i].to);

        ans[k]=max(ans[k],ans[edge[i].to]);

        add(edge[i].to,delta,-);

    }

    int delta=;

    if (son[k])

    {

        delta=dfs(son[k])^(<<len[son[k]]);ans[k]=max(ans[k],ans[son[k]]);

        for (int i=p[k];i;i=edge[i].nxt)

        if (edge[i].to!=son[k])

        {

            ans[k]=max(ans[k],calc(edge[i].to,delta^(<<len[edge[i].to]))-(deep[k]<<));

            add(edge[i].to,delta^(<<len[edge[i].to]),);

        }

    }

    ans[k]=max(ans[k],f[delta]-deep[k]);

    for (int i=;i<;i++) ans[k]=max(ans[k],f[delta^(<<i)]-deep[k]);

    update(delta,deep[k],);

    return delta;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("741D.in","r",stdin);

    freopen("741D.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<=n;i++)

    fa[i]=read(),addedge(fa[i],i,getc()-'a');

    deep[]=;make();

    dfs();

    for (int i=;i<=n;i++) printf("%d ",ans[i]);

    return ;

}

相关文章