题解 P5018 【对称二叉树】

· · 题解

好像没有树哈希，那我就来发一份。

树哈希是一种直接在树上进行 哈希的方法，从而判断是否同构。举个例子（二叉树）：hash[x]=(hash[x.lson]*998244353+hash[x.rson]*1000000007+x.val)\mod M。M可以取一个很大的数，如(1<<64)-1。如果hash[a]==hash[b]，就可以判断以a,b为根的子树同构（对应位置上的节点完全相等）。

但现在是判断是否对称。于是，我们令invhash[x]表示把以x为根的子树对称后的hash值。像上面一样写出式子：invhash[x]=(invhash[x.rson]*998244353+invhash[x.lson]*1000000007+x.val)\mod M。x为根的二叉子树是对称二叉子树的必要条件是hash[x.lson]==invhash[x.rson]。用这个条件来判断，写出下面的代码我才不会告诉你它不能A掉这道题：

#include<bits/stdc++.h>
using namespace std;
struct node {
    int val, num;
    int ls, rs;
    unsigned long long hash, invhash;
}nd[1000001];
void dfs(int node) {
    if (node == 0) return;
    if (nd[node].ls == -1) nd[node].ls = 0;
    if (nd[node].rs == -1) nd[node].rs = 0;
    dfs(nd[node].ls), dfs(nd[node].rs);
    nd[node].num = nd[nd[node].ls].num + nd[nd[node].rs].num + 1;
    nd[node].hash=nd[nd[node].ls].hash*998244353+nd[nd[node].rs].hash*1000000007+nd[node].val;
    nd[node].invhash=nd[nd[node].ls].invhash*1000000007+nd[nd[node].rs].invhash*998244353+nd[node].val;
}
int main() {
    freopen("test.in","r",stdin);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> nd[i].val;
    for (int i = 1; i <= n; i++) cin >> nd[i].ls >> nd[i].rs;
    dfs(1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (nd[nd[i].ls].hash == nd[nd[i].rs].invhash) ans = max(ans, nd[i].num);
    cout << ans << endl;
}

于是，我们需要打表多选几个模数。这样就能A掉这道题。