- 科技
- 【模板】树哈希
OI Wiki - 树哈希
板子
#include <bits/stdc++.h>
using namespace std
;
typedef unsigned long long ull
;
typedef long long ll
;
const int INF
= 0x3f3f3f3f;
const ll inf
= (1ll << 60);
const int N
= 1e6 + 10;
vector
<int> e
[N
];
int n
, m
;
namespace treeHash
{
int primes
[N
], cnt
;
bool st
[N
];
void get_primes(int n
) {
for (int i
= 2; i
<= n
; i
++) {
if (!st
[i
]) primes
[++cnt
] = i
;
for (int j
= 1; primes
[j
] <= n
/ i
; j
++) {
st
[primes
[j
] * i
] = true;
if (i
% primes
[j
] == 0) break;
}
}
}
int Mx
[N
], sz
[N
], root
;
void calcSize(int u
, int fa
) {
sz
[u
] = 1, Mx
[u
] = 0;
for (int i
= 0, lim
= e
[u
].size(); i
< lim
; i
++) {
int v
= e
[u
][i
];
if (v
!= fa
&& v
) {
calcSize(v
, u
);
Mx
[u
] = max(Mx
[u
], sz
[v
]);
sz
[u
] += sz
[v
];
}
}
Mx
[u
] = max(Mx
[u
], n
- sz
[u
]);
if (Mx
[u
] < Mx
[root
]) {
root
= u
;
}
}
ull Hash
[N
];
ull
getTreeHash(int u
, int fa
) {
sz
[u
] = 1;
ull res
= 1;
for (int i
= 0, lim
= e
[u
].size(); i
< lim
; i
++) {
int v
= e
[u
][i
];
if (v
!= fa
&& v
) {
res
+= getTreeHash(v
, u
) * primes
[sz
[v
]];
sz
[u
] += sz
[v
];
}
}
return res
;
}
}
using namespace treeHash
;
int main() {
ios
::sync_with_stdio(false);
cin
.tie(0), cout
.tie(0);
get_primes(100000);
cin
>> m
;
for (int i
= 1; i
<= m
; i
++) {
cin
>> n
;
for (int v
= 1, u
; v
<= n
; v
++) {
cin
>> u
;
e
[u
].push_back(v
);
e
[v
].push_back(u
);
}
Mx
[root
= 0] = INF
;
calcSize(1, 0);
Hash
[i
] = inf
;
for (int j
= 1; j
<= n
; j
++) {
if (Mx
[j
] == Mx
[root
]) {
Hash
[i
] = min(Hash
[i
], getTreeHash(j
, 0));
}
}
for (int j
= 1; j
<= i
; j
++) {
if (Hash
[i
] == Hash
[j
]) {
cout
<< j
<< endl
;
break;
}
}
for (int j
= 0; j
<= n
; j
++) {
e
[j
].clear();
}
}
return 0;
}
Processed:
0.013, SQL:
9
