想到了一个问题,如果权值全部为 1,且某两个子树大小相同但形态不同,我就会判断失误。
by __vector__ @ 2022-12-30 14:25:53
我加个树哈希试试
by __vector__ @ 2022-12-30 14:58:35
加了树哈希之后变成了 72 分。
by __vector__ @ 2022-12-30 15:08:58
更新之后的代码:
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353,mod2=1e9+7,seed=998244353;
const int maxn=1e6+5;
int n;
int v[maxn];
struct Tree
{
int ls,rs;
}tree[maxn];
ll pow10[maxn],pow10_2[maxn];
ll hash1[maxn],hash3[maxn];
ll hashform[maxn];
int size[maxn];
void dfs(int node)
{
if(node==-1)return;
dfs(tree[node].ls);
if(tree[node].ls!=-1)
{
hash1[node]=hash1[tree[node].ls]*10ll+(ll)v[node];
hash1[node]%=mod;
hash3[node]=hash3[tree[node].ls]*10ll+(ll)v[node];
hash3[node]%=mod2;
}
else
{
hash1[node]=v[node];
hash3[node]=v[node];
}
dfs(tree[node].rs);
hash1[node]=hash1[node]*pow10[size[tree[node].rs]]+hash1[tree[node].rs];
hash1[node]%=mod;
hash3[node]=hash3[node]*pow10_2[size[tree[node].rs]]+hash3[tree[node].rs];
hash3[node]%=mod2;
}
ll hash2[maxn],hash4[maxn];
void dfs2(int node)
{
if(node==-1)return;
dfs2(tree[node].rs);
if(tree[node].rs!=-1)
{
hash2[node]=hash2[tree[node].rs]*10ll+(ll)v[node];
hash2[node]%=mod;
hash4[node]=hash4[tree[node].rs]*10ll+(ll)v[node];
hash4[node]%=mod;
}
else
{
hash2[node]=v[node];
hash4[node]=v[node];
}
dfs2(tree[node].ls);
hash2[node]=hash2[node]*pow10[size[tree[node].ls]]+hash2[tree[node].ls];
hash2[node]%=mod;
hash4[node]=hash4[node]*pow10_2[size[tree[node].ls]]+hash4[tree[node].ls];
hash4[node]%=mod;
}
void dfs3(int node)
{
if(node==-1)return;
size[node]=1;
dfs3(tree[node].ls);
dfs3(tree[node].rs);
if(tree[node].ls!=-1)
size[node]+=size[tree[node].ls];
if(tree[node].rs!=-1)
size[node]+=size[tree[node].rs];
}
int ans=0;
void dfs4(int node)
{
if(node==-1)return;
if(size[tree[node].ls]==size[tree[node].rs])
{
if(tree[node].ls!=-1&&tree[node].rs!=-1)
{
if(hash1[tree[node].ls]==hash2[tree[node].rs]&&hash3[tree[node].ls]==hash4[tree[node].rs])
{
if(hashform[tree[node].ls]==hashform[tree[node].rs])
{
ans=max(ans,size[node]);
}
}
}
if(tree[node].ls==-1&&tree[node].rs==-1)
{
ans=max(ans,1);
}
}
dfs4(tree[node].ls);
dfs4(tree[node].rs);
}
void dfs5(int node)
{
if(node==-1)return;
dfs5(tree[node].ls);
dfs5(tree[node].rs);
if(tree[node].ls==tree[node].rs&&tree[node].rs==-1)
{
hashform[node]=1;
return;
}
ll a=1;
if(tree[node].ls!=-1)
{
a=hashform[tree[node].ls];
}
ll b=1;
if(tree[node].rs!=-1)
{
b=hashform[tree[node].rs];
}
hashform[node]=(a*seed+size[tree[node].ls])^(b*seed+size[tree[node].rs]);
hashform[node]%=mod;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d%d",&tree[i].ls,&tree[i].rs);
}
pow10[0]=1;
for(int i=1;i<=n;i++)
{
pow10[i]=pow10[i-1]*10ll%mod;
}
pow10_2[0]=1;
for(int i=1;i<=n;i++)
{
pow10_2[i]=pow10_2[i-1]*10ll%mod2;
}
dfs3(1);
dfs(1);
dfs2(1);
dfs5(1);
dfs4(1);
printf("%d",ans);
return 0;
}
```
by __vector__ @ 2022-12-30 15:09:58