1 条题解

  • 0
    @ 2026-10-26 9:00:01

    摘自《浅谈哈希》。

    树哈希

    P5043 【模板】树同构 / [BJOI2015] 树的同构

    思考如何把一棵无根树映射到一个整数,感觉很难做。不妨把重心作为根,求出有根树哈希值(双重心把两个哈希值打包即可)。我们有这样一个正统的有根树多项式哈希函数:

    $$H(u) = \left(1+\sum_{i} H(\text{son}(u,i)) \times b^{i}\right) \bmod M $$

    其中 son(u,i)\text{son}(u,i) 表示 uu 的儿子按哈希值排序后的第 ii 个儿子编号。最劣复杂度 Θ(nlog⁡n)\Theta(n\log n)。原理其实就是不让节点编号影响哈希值。

    #include<iostream>
    #include<algorithm>
    #include<vector>
    #include<queue> 
    #include<map>
    #include<random>
    #define int long long
    #define ull unsigned long long
    using namespace std;
    const int base=3;
    int n,m,maxx,cnt,id[57],fa[57],sz[57];
    ull h[57];
    vector<int> tr[57];
    vector<ull> hs;
    map<ull,int> mp;
    void DFS1(int u,int f){
    	sz[u]=1;
    	int x=-1;
    	for(int v : tr[u]){
    		if(v==f) continue;
    		DFS1(v,u);
    		sz[u]+=sz[v];
    		x=max(x,sz[v]);
    	}
    	x=max(x,n-sz[u]);
    	if(x>maxx) maxx=x,id[cnt=1]=u;
    	else if(x==maxx) id[++cnt]=u;
    }
    void DFShs(int u,int f){
    	h[u]++;
    	for(int v : tr[u]) if(v!=f) DFShs(v,u);
    	sort(tr[u].begin(),tr[u].end(),[](int x,int y){
    		return h[x]<h[y];
    	});
    	ull p=1;
    	for(int v : tr[u]){
    		if(v==f) continue;
    		h[u]+=h[v]*p;
    		p=p*base;
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cin>>m;
    	for(int t=1;t<=m;t++){
    		cin>>n;
    		for(int i=0;i<=n;i++) tr[i].clear();
    		int root;
    		for(int i=1;i<=n;i++){
    			cin>>fa[i];
    			if(fa[i]){
    				tr[fa[i]].push_back(i);
    				tr[i].push_back(fa[i]);
    			}
    			else root=i;
    		}
    		maxx=-1,cnt=0;
    		DFS1(root,0);
    		int res=0;
    		for(int i=1;i<=cnt;i++){
    			for(int j=0;j<=n;j++) h[j]=0;
    			DFShs(id[i],0);
    			res+=h[id[i]];
    		}
    		if(!mp[res]) mp[res]=t;
    		cout<<mp[res]<<'\n';
    	}
    	
    	return 0;
    }
    

    另外附一个好写且卡不掉的严格线性树哈希,OI-wiki 也改成这个了,可以学一学。

    推荐例题 P4323。

    • 1

    信息

    ID
    159
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    15
    已通过
    7
    上传者