我用单哈希竟然直接过了对称二叉树这道题,记录
我想问一下,我这个哈希代码,能不能构造一组数据卡掉它?
#include<bits/stdc++.h>
// 一些随便找的质数
#define p1 167772161ull
#define p2 469762049ull
#define p3 754974721ull
using namespace std;
typedef unsigned long long ull;
int n,v[1000005],l[1000005],r[1000005],size[1000005];
ull h[1000005],hinv[1000005];
int read() {
char c=getchar();
int n=0,f=1;
while(c<48) {
if(c == '-') f=-1;
c=getchar();
}
while(c>47) n=n*10+(c^48), c=getchar();
return n*f;
}
void dfs(int rt) {
size[rt]=1;
h[rt]=hinv[rt]=v[rt]*p3;
if(~l[rt]) {
dfs(l[rt]);
size[rt]+=size[l[rt]];
h[rt]+=h[l[rt]]*p1;
hinv[rt]+=hinv[l[rt]]*p2;
}
if(~r[rt]) {
dfs(r[rt]);
size[rt]+=size[r[rt]];
h[rt]+=h[r[rt]]*p2;
hinv[rt]+=hinv[r[rt]]*p1;
}
h[rt] ^= 999999786000011449;
hinv[rt] ^= 999999786000011449;
}
int main() {
n=read();
for(int i=1; i<=n; i++) v[i]=read();
for(int i=1; i<=n; i++) l[i]=read(), r[i]=read();
dfs(1);
int ans=1;
for(int i=1; i<=n; i++)
if(h[l[i]] == hinv[r[i]])
ans = max(ans,size[i]);
cout<<ans;
}