树哈希
题意：
判断树是否是对称的
做法一：随机种子+shift
cpp
mt19937_64 rng(time(0));
ULL shift(ULL x){
x^=x<<13,x^=x>>7,x^=x<<17;
return x;
}
void solve(){
int n;
cin>>n;
vector<int> adj[n+1];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
ULL seed=rng();
vector<int> sym(n+1);
vector<ULL> h(n+1);
function<void(int,int)> dfs=[&](int u,int fa){
ULL sum=seed,xsum=0;
for(auto v:adj[u]){
if(v==fa)continue;
dfs(v,u);
sum+=shift(h[v]),xsum^=shift(h[v]);
}
h[u]=sum;
if(!xsum){
sym[u]=1;
return;
}
for(auto v:adj[u]){
if(v==fa)continue;
if(xsum==shift(h[v])&&sym[v]){
sym[u]=1;
return;
}
}
};
dfs(1,0);
cout<<(sym[1]?"YES\n":"NO\n");
}做法二：AHU算法 $ O(nlogn) $
- 严格正确
- 使用
map<vector<int>,int>
cpp
void solve(){
int n;
cin>>n;
vector<int> adj[n+1];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
map<vector<int>,int> mp;
vector<int> h(n+1),sym(n+1);
int idx=0;
auto get=[&](vector<int> &v){
if(!mp.count(v))mp[v]=++idx;
return mp[v];
};
function<void(int,int)> dfs=[&](int u,int fa){
vector<int> tmp;
map<int,int> cnt;
for(auto v:adj[u]){
if(v==fa)continue;
dfs(v,u);
tmp.push_back(h[v]);
}
sort(tmp.begin(),tmp.end());
h[u]=get(tmp);
for(auto v:adj[u]){
if(v==fa)continue;
cnt[h[v]]++;
}
int cur=0,p;
for(auto [x,y]:cnt){
if(y&1)cur++,p=x;
}
if(!cur){
sym[u]=1;
return;
}
if(cur==1){
for(auto v:adj[u]){
if(v==fa)continue;
if(h[v]==p&&sym[v]){
sym[u]=1;
return;
}
}
}
};
dfs(1,0);
cout<<(sym[1]?"YES\n":"NO\n");
}