树同构

约 296 个字 16 行代码 预计阅读时间 1 分钟

树哈希

以 $rt$ 为根的子树，假设儿子是 $v_1, v_2, \cdots, v_k$，定义子树的哈希 $h(rt)=1+\sum\limits_{i=1}^k f(h(v_i))$。其中 $h(v_i)$ 是 $v_i$ 对应子树的哈希，$f$ 为一个待定函数。如果需要换根，第二次 dp 时只需把子树哈希减掉即可

ll g(ll x) {return x * x * x * 1237123 + 19260817;}
ll f(ll x) {return g(x & ((1 << 31) - 1)) + g(x >> 31);}

AHU

我们考虑，给每个点一个标号，使得同构子树的根，标号相同。

怎么做到呢？对于一个点 u，把它的儿子的标号拎出来塞进一个vector里面，然后把vector排序，那么这个vector就是 u 的标号了！

但是拿vector当标号未免有点离谱，而且会出现vector套娃的情况。所以我们把每个vector用map进行编号就行了

两棵树用同一个map跑才能判断

无根树，如果单重心，则以重心为根；否则在两个重心中间那条边上建一个虚点做根

注意要把虚点特殊处理（比如往它的vector里塞个-1），不然会出现把两个点的链和三个点的链判成同构

总复杂度 $O(nlog n)$

int hsh[N],idc;
map<vector<int>,int> id;
void dfs(int u,int fa){
    vector<int> tmp;
    for(auto &G[u])if(v!=fa)
    {
        dfs(v,u);
        tmp.push_back(hsh[v]);
    }
    sort(tmp.begin(),tmp.end());
    int &x=id[tmp];
    if(!x) x=++idc;
    hsh[u]=x;
}