树的重心
定义：以这个点为根时，树各节点深度之和最小的点叫树的重心。
以这个点为根时，最大的子树最小的点叫树的重心。
以这个点为根时，所有子树大小不超过 \(n/2\) 的点叫树的重心。
为什么这仨是一回事？
我们拿第一个定义的换根dp方程来说明这三个定义等价。
注意到，如果存在一个 \(v\)，使得 \(2\times siz[v]>n\)，那么如果往这里遍历，\(dp[v]\)会变小。否则 \(dp[v]\) 就会变大。
注意到，这样的 \(v\) 有且仅有1个。
这说明在这个点，所有点与它的距离最小。并且所有子树的大小都不超过 \(n/2\) 。 根据 \(siz[v]\times 2\le n\) 得到。
还可以进一步分析得到问题二。
如果这个点上下移动了，只有两种情况：
-
子树中有 size 等于 n/2 的子树
-
子树中所有子树 size 都小于 n/2
不论以上哪种情况，往任意子树方向走，都会让最大的子树的大小变大（最少都是不变）。
比较显然就不画图了。
树的同构
对于结构相同，节点编号可能不同的两棵树，我们称它们是同构的。
例子：
我们认为这两棵树同构。（上图是无根树）
有根树的同构判断
括号序列表示树
很简单，举个例子就能看懂。
对于每个叶子结点，我们用 () 表示。对于每个节点，我们依次写出它们的子节点的子树的表示，然后用一个括号括起来。
如上图的 \(u\) 节点，我们用 ( () (()()()) (()()) ) 表示以 \(u\) 为根的子树（实际实现中不加空格，这里为了方便阅读就加了空格）。
上图整颗树的括号序列为 ((()(()()())((())))(()()))。
求出有根树的括号序列，判断是否相同，就可以知道两棵树的结构是否相同啦！
注意 \(u\) 的各个子树的括号序列要排序，因为可能访问顺序不同。
时间复杂度：\(O(n^2\log n)\)，每访问一个节点排一次序。
点击展开代码
//根为1
#include<bits/stdc++.h>
using namespace std;
struct tree{int n;string ans[100005];vector<int> g[100005];void init(){cin>>n;for(int i=1,x,y;i<n;++i){cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}}void dfs(int u,int Fa){vector<string> tmp;for(auto v:g[u]){if(v==Fa) continue; dfs(v,u);tmp.push_back(ans[v]);} sort(tmp.begin(),tmp.end());ans[u]="(";for(auto v:tmp) ans[u]+=v;ans[u]+=")";}
}t1,t2;
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);t1.init();t2.init();t1.dfs(1,0);t2.dfs(1,0);if(t1.ans[1]==t2.ans[1]) cout<<"Yes";else cout<<"No";cout<<"\n"<<t1.ans[1]<<"\n"<<t2.ans[1];return 0;
}
哈希判断同构
我们设单个节点的哈希值为常数 1。
如果已有 \(u\) 子树 \(v\) 的 哈希值 \(ans[v]\)，如何得到 \(u\) 的哈希值？
可以采用加和。
实际实现中，累加子树哈希值之前，对子树哈希的值再进行一次哈希。
一个好用的二进制打乱函数以及不容易被卡的随机函数。
using ull=unsigned long long;
const ull mod=mt19937_64(time(0))();
ull f(ull t){t^=mod;t^=t<<13;t^=t>>7;t^=t<<17;t^=mod;return t;
}
最终哈希公式：
时间复杂度：\(O(n)\)
点击展开代码
//默认根为1
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
struct tree{int n; ull mod=mt19937_64(time(0))();ull ans[1000005];vector<int> g[1000005];void init(){cin>>n;for(int i=1,x,y;i<n;++i){cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}}ull shufule(ull t){t^=mod;t^=t<<13;t^=t>>7;t^=t<<17;t^=mod;return t;}void dfs(int u,int Fa){ans[u]=1;for(auto v:g[u]){if(v==Fa) continue; dfs(v,u);ans[u]+=shufule(ans[v]);}}
}t1,t2;
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);t1.init();t2.init();t1.dfs(1,0);t2.dfs(1,0);if(t1.ans[1]==t2.ans[1]) cout<<"YES";else cout<<"NO"; return 0;
}
无根树判断同构
考虑转化为有根树判断同构。
如何选根节点？肯定要选一个特殊且在树上唯一的节点。
想到了树的重心，虽然可能有两个，但是可以把两个重心都当做根判断一遍。
例题：SP7826 TREEISO - Tree Isomorphism
就是让你判断两棵无根树是否同构。
点击展开代码
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
int n;
vector<int> g[500005];
ull siz[500005],maxv[500005];
mt19937_64 rng(time(0));
ull mod=rng();
ull shufule(ull t){t^=mod;t^=t<<13;t^=t>>7;t^=t<<17;t^=mod;return t;
}
void dfs1(int u,int Fa,vector<ull> &w){siz[u]=1;maxv[u]=0;for(int v:g[u]){if(v==Fa) continue;dfs1(v,u,w);siz[u]+=siz[v];maxv[u]=max(maxv[u],siz[v]);}maxv[u]=max(maxv[u],n-siz[u]);if(maxv[u]<=n/2) w.push_back(u);
}
ull get_hash(int u,int Fa){ull res=1;for(auto v:g[u]){if(v==Fa) continue;res+=shufule(get_hash(v,u));}return res;
}
pair<ull,ull> solve(){if(n==1) return {0,1};for(int i=1,x,y;i<n;i++){cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}vector<ull> w;dfs1(1,0,w);ull h1=get_hash(w[0],0);if(w.size()==h1) return {0,h1};ull h2=get_hash(w[1],0);return {min(h1,h2),max(h1,h2)};
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int T;cin>>T;while(T--){fill(siz+1,siz+1+n,0);fill(maxv+1,maxv+1+n,0);cin>>n;for(int i=1;i<=n;i++) g[i].clear();auto h1=solve();for(int i=1;i<=n;i++) g[i].clear();auto h2=solve();cout<<(h1==h2?"YES":"NO")<<"\n";}return 0;
}