# 任意点为根的hash值

(f[i])表示以(i)为根时整棵树的hash值。然后就有(f[v] = (f[u] - hs[v] * prime[siz[v]]) * prime[n-siz[v]] + hs[v])

# 例题

luogu5043

``````/*
* @Author: wxyww
* @Date: 2020-03-06 16:59:41
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<map>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 110;
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int pri[N * N],vis[N * N];

void pre() {
int tot = 0;
for(int i = 2;i <= 10000;++i) {
if(!vis[i]) pri[++tot] = i;
for(int j = 1;j <= tot && pri[j] * i <= 10000;++j) {
vis[pri[j] * i] = 1;
if(i % pri[j] == 0) break;
}
}
}
vector<int>e[N];
map<ull,int>ma;
int siz[N];
ull hs[N];
int n,root1,root2;
void dfs(int u,int fa) {
siz[u] = 1;
for(vector<int>::iterator it = e[u].begin();it != e[u].end();++it) {
if((*it == fa) || (*it == root1 && u) || (*it == root2 && u)) continue;
dfs(*it,u);
hs[u] += hs[*it] * pri[siz[*it]];
siz[u] += siz[*it];
}
hs[u]++;
}
void get1(int u,int fa) {
siz[u] = 1;
for(vector<int>::iterator it = e[u].begin();it != e[u].end();++it) {
if(*it == fa) continue;
get1(*it,u);
siz[u] += siz[*it];
}
}
void get2(int u,int fa) {
int mx = n - siz[u];
for(vector<int>::iterator it = e[u].begin();it != e[u].end();++it) {
if(*it == fa) continue;
get2(*it,u);
mx = max(mx,siz[*it]);
}
if(mx <= n / 2) {
if(!root1) root1 = u;
else root2 = u;
}
}
int main() {
pre();
for(int i = 1;i <= T;++i) {
memset(hs,0,sizeof(hs));
for(int i = 0;i <= n;++i) e[i].clear();
for(int i = 1;i <= n;++i) {
if(!x) continue;
e[x].push_back(i);
e[i].push_back(x);
}
root1 = 0,root2 = 0;
get1(1,0);
get2(1,0);
e[0].push_back(root1);
if(root2) e[0].push_back(root2);
dfs(0,0);
if(!ma[hs[0]]) ma[hs[0]] = i;
printf("%d
",ma[hs[0]]);
}
return 0;
}``````

luogu4323

`````` /*
* @Author: wxyww
* @Date: 2020-03-06 19:31:22
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<map>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 200010;
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int siz[N];
vector<int>e1[N],e2[N];
map<ull,bool>ma;
ull f[N],hs[N];
int vis[N * 10],pri[N * 10];
void pre() {
int tot = 0;
for(int i = 2;i < N * 10;++i) {
if(!vis[i]) pri[++tot] = i;
for(int j = 1;j <= tot && pri[j] * i < N * 10;++j) {
vis[pri[j] * i] = 1;
if(i % pri[j] == 0) break;
}
}
}
int n;
void dfs1(int u,int fa) {
siz[u] = 1;
for(vector<int>::iterator it = e1[u].begin();it != e1[u].end();++it) {
if(*it == fa) continue;
dfs1(*it,u);
hs[u] += hs[*it] * pri[siz[*it]];
siz[u] += siz[*it];
}
hs[u]++;
}

void dfs2(int u,int fa) {
ma[f[u]] = true;
for(vector<int>::iterator it = e1[u].begin();it != e1[u].end();++it) {
if(*it == fa) continue;
f[*it] = (f[u] - pri[siz[*it]] * hs[*it]) * pri[n - siz[*it]] + hs[*it];
dfs2(*it,u);
}
}
void dfs3(int u,int fa) {
siz[u] = 1;
for(vector<int>::iterator it = e2[u].begin();it != e2[u].end();++it) {
if(*it == fa) continue;
dfs3(*it,u);
hs[u] += hs[*it] * pri[siz[*it]];
siz[u] += siz[*it];
}
hs[u]++;
}
int ans[N];
void dfs4(int u,int fa) {
if(e2[u].size() == 1 && ma[f[u] - 1]) ans[u] = 1;
for(vector<int>::iterator it = e2[u].begin();it != e2[u].end();++it) {
if(*it == fa) continue;
f[*it] = (f[u] - pri[siz[*it]] * hs[*it]) * pri[n + 1 - siz[*it]] + hs[*it];
dfs4(*it,u);
}
}
int main() {
pre();
for(int i = 1;i < n;++i) {
e1[u].push_back(v);
e1[v].push_back(u);
}
for(int i = 1;i <= n;++i) {
e2[u].push_back(v);
e2[v].push_back(u);
}
dfs1(1,0);
f[1] = hs[1];
dfs2(1,0);
memset(hs,0,sizeof(hs));
memset(f,0,sizeof(f));
dfs3(1,0);
f[1] = hs[1];
dfs4(1,0);
for(int i = 1;i <= n + 1;++i) {
if(ma[f[i] - 2]) {
for(vector<int>::iterator it = e2[i].begin();it != e2[i].end();++it) {
if(e2[*it].size() == 1) ans[*it] = 1;
}
}
}
for(int i = 1;i <= n + 1;++i) {
if(ans[i]) {
printf("%d
",i);return 0;
}
}
return 0;
}``````