树哈希过了,但感觉写假了
查看原帖
树哈希过了,但感觉写假了
513717
Str_ywr楼主2023/8/8 16:05

问一下,这个哈希能卡掉吗?

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read() {
	   ll x = 0,f = 1;
	   char ch = getchar();
	   while(ch < '0' ||ch > '9') {
			if(ch == '-') f = -1;
			ch = getchar();
	   }
	   while(ch >= '0' && ch <= '9') {
			x = (x << 1) + (x << 3) + (ch ^ '0');
			ch = getchar();
	   }
	   return x * f;
}
mt19937 seed(time(0));
ull rnd(ull x,ull y) {
	return uniform_int_distribution <ull> (x,y)(seed);
}
const int N = 1e6 + 10, base = 13331; const ull mask = rnd(1e16,1e18);
int n; int a[N]; int lson[N], rson[N];
int ans = 1;
inline ull gethash(ull x) {
	x ^= mask; x ^= x<<13;
	x ^= x>>7; x ^= x<<17;
	x ^= mask; return x;
}
int sz[N];
ull dfs(int x,int fa,bool isl) {
	ull ha = a[x] * base * base; ull lha = 0,rha = 0; sz[x] = 1;//如果空节点是1冲突了???
	if (lson[x] != -1) {
		lha = dfs(lson[x], x, 1);
		sz[x] += sz[lson[x]];
	}
	if (rson[x] != -1) {
		rha = dfs(rson[x], x, 0);
		sz[x] += sz[rson[x]];
	}
	if (lha == rha) ans = max(ans, sz[x]); 
	if (isl) {
		ha += gethash(lha) * base + gethash(rha);
	}else {
		ha += gethash(rha) * base + gethash(lha);
	}
	return ha;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	for (int i = 1; i <= n; i++) {
		lson[i] = read(), rson[i] = read();
	}
	dfs(1, 0, 1);	
	cout << ans;
	return 0;
}


2023/8/8 16:05
加载中...