P5043 [BJOI2015]树的同构(树哈希模版)

*原题链接*

树哈希模版题

树哈希是解决树同构问题的利器，可以有效降低时间复杂度，简化操作。不过如果哈希方法不合适的话，很容易被卡。我写的是oiwiki上推荐的哈希方法。在此放上链接——树哈希

对于这道题，数据范围极小，可以暴力对每棵树每个点为根都进行一遍哈希，如果稍大的话，可以换根dp来优化，最后将多重集的哈希值算出来。如果会树哈希的话，这道题的代码也很好写。

时间复杂度，非常高效。

#include<cstdio>
#include<chrono>
#include<map>
#include<vector>
#include<iostream>
using namespace std;
#define ull unsigned long long
const int N=110;
const ull mask=chrono::steady_clock::now().time_since_epoch().count();int read(){int 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*10+ch-'0',ch=getchar();return x*f;
}int m,n;ull sub[N],root[N];
vector<int> edge[N];
map<ull,int> mp;ull shift(ull x){x^=mask;//亲测不异或mask也可以过x^=(x<<13);x^=(x>>7);x^=(x<<17);x^=mask;return x;
}void dpsub(int x){sub[x]=1;for(auto v:edge[x]){dpsub(v);sub[x]+=shift(sub[v]);}
}void dproot(int x){//换根dpfor(auto v:edge[x]){root[v]=sub[v]+shift(root[x]-shift(sub[v]));dproot(v);}
}int main(){m=read();for(int i=1;i<=m;i++){n=read();int rt;for(int j=1;j<=n;j++){int x=read();if(!x) rt=j;edge[x].push_back(j);}dpsub(rt);root[rt]=sub[rt];dproot(rt);ull hash=1;for(int j=1;j<=n;j++) hash+=shift(root[j]);//计算多重集的哈希值if(!mp.count(hash)) mp[hash]=i;cout<<mp[hash]<<endl;for(int j=1;j<=n;j++) edge[j].clear();//别忘了清空}return 0;
}