[NOIP2018PJ]对称二叉树

这个题正常人看到题面难道不是哈希?

乱写了个树哈希...

#include<bits/stdc++.h>

using namespace std;

const int _=1e6+5,p=998244353;

int re(){

    int x=0,w=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*w;

}

int n,ans=1,w[_],ls[_],rs[_],sz[_],f[_],g[_],h[_];

void init(int u){

    sz[u]=1;

    if(ls[u]>0){init(ls[u]);sz[u]+=sz[ls[u]];h[u]++;}

    if(rs[u]>0){init(rs[u]);sz[u]+=sz[rs[u]];h[u]++;}

}

void calc(int u){

    f[u]=w[u]*233+sz[u]*(19+h[u]);

    if(ls[u]>0){

        calc(ls[u]);

        f[u]=1ll*f[u]*17%p+f[ls[u]]%p;

    }

    if(rs[u]>0){

        calc(rs[u]);

        f[u]=1ll*f[u]*f[u]%p+f[rs[u]]%p;

    }

}

void dfs(int u){

    if(ls[u]>0)dfs(ls[u]);

    if(rs[u]>0)dfs(rs[u]);

    swap(ls[u],rs[u]);

}

int main(){

    n=re();

    for(int i=1;i<=n;i++)w[i]=re();

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

        ls[i]=re(),rs[i]=re();

    init(1);calc(1);

    for(int i=1;i<=n;i++)g[i]=f[i];

    dfs(1);calc(1);

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

        if(f[i]==g[i])ans=max(ans,sz[i]);

    printf("%d\n",ans);

    return 0;

}

巴特西

[NOIP2018PJ]对称二叉树

[NOIP2018PJ]对称二叉树

最新文章

热门文章