树hash 68分求调!!!(代码易懂有注释)
查看原帖
树hash 68分求调!!!(代码易懂有注释)
566243
zzx12345678楼主2023/10/4 20:58

麻烦大佬们看下为什么会wa,谢谢了

#include <bits/stdc++.h>
#define N 2000005
#define ll long long
#define mod 755039707
using namespace std;
ll n,u,v;
ll ans;
ll a[N]; 
ll siz[N],zuo[N],you[N],has[N];
//siz记录子树大小,zuo\you数组记录u节点的左右儿子 ,has是hash数组 
void dfs(ll u){
	if(zuo[u]!=0)dfs(zuo[u]);
	if(you[u]!=0)dfs(you[u]);//递归 
	siz[u]=siz[zuo[u]]+siz[you[u]]+1;//统计树大小 
	
	has[u]=a[zuo[u]]*7503707+a[you[u]]*7503707+has[zuo[u]]+has[you[u]]+a[u];//hash
	has[u]%=mod;
	
	if((a[zuo[u]]==a[you[u]])&&(has[zuo[zuo[u]]]==has[you[you[u]]])&&(has[zuo[you[u]]]==has[you[zuo[u]]])){
		ans=max(ans,siz[u]);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&u,&v);
		if(u!=-1){
			zuo[i]=u;
		}
		if(v!=-1){
			you[i]=v;
		}
	}
	dfs(1);
	cout<<ans<<endl;
    return 0;
}
2023/10/4 20:58
加载中...