AIOJ

When testing whether trees are isomorphic, we often convert them into hash values and store those values to reduce complexity.

Tree hashing is highly flexible, and many different hash schemes can be designed. However, an arbitrary design can easily be incorrect or be defeated by adversarial data. The method below is easy to implement and difficult to defeat.

Method

This method requires a hash function for multisets. The hash of the subtree rooted at a vertex is the hash of the multiset formed by the hashes of the subtrees rooted at all its children, that is:

h_x = f(\{ h_i \mid i \in son(x) \})

Here, $h_x$ denotes the hash of the subtree rooted at $x$ , and $f$ is the multiset hash function.

For example, consider the hash function used in the code:

f(S) = \left( c + \sum_{x \in S} g(x) \right) \bmod m

Here, $c$ is a constant, for which $1$ is generally sufficient. $m$ is the modulus; $2^{32}$ or $2^{64}$ can generally be used with natural overflow, or a large prime can be used. $g$ maps integers to integers; the code uses xor shift. Other functions are possible, but polynomial functions are not recommended. To prevent a problem setter from defeating the xor hash, one can also xor a random constant before and after the mapping.

This hash is very easy to implement. If rerooting is needed, during the second DP we only need to subtract the subtree hash.

Examples

UOJ #763. Tree Hashing

This is a template problem. There is little more to say: simply run a DFS rooted at $1$ .

Reference implementation

#include <cctype>
#include <iostream>
#include <random>
#include <set>
#include <vector>

using ull = unsigned long long;

const ull mask = std::mt19937_64(time(nullptr))();

ull shift(ull x) {
  x ^= mask;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  x ^= mask;
  return x;
}

constexpr int N = 1e6 + 10;

int n;
ull hash[N];
std::vector<int> edge[N];
std::set<ull> trees;

void getHash(int x, int p) {
  hash[x] = 1;
  for (int i : edge[x]) {
    if (i == p) {
      continue;
    }
    getHash(i, x);
    hash[x] += shift(hash[i]);
  }
  trees.insert(hash[x]);
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  getHash(1, 0);
  cout << trees.size();
}

[BJOI2015] Tree Isomorphism

The isomorphism in this problem concerns unrooted trees, whereas the method above targets rooted trees. Thus, two isomorphic unrooted trees have equal hashes only when their roots are the same. Since the data range is small, we can brute-force the hash with every vertex as the root, then sort and compare the results.

If the data range is larger, we can use rerooting DP: traverse the tree twice and compute the hash with every vertex as the root. We can also use the multiset hash above: store the hash for every possible root in a multiset, then compute the hash of that multiset and compare it (method 1).

The complexity can also be improved by finding the centroid. A tree has at most two centroids, so it is enough to compute the hash with each centroid as the root. We can then either compare these hashes separately (method 2), or use the hash of the single centroid as the hash of the whole tree; with two centroids, use the smaller (or larger) of the two.

Method 1

#include <iostream>
#include <map>
#include <random>
#include <vector>

using ull = unsigned long long;

constexpr int N = 60, M = 998244353;
const ull mask = std::mt19937_64(time(nullptr))();

ull shift(ull x) {
  x ^= mask;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  x ^= mask;
  return x;
}

std::vector<int> edge[N];
ull sub[N], root[N];
std::map<ull, int> trees;

void getSub(int x) {
  sub[x] = 1;
  for (int i : edge[x]) {
    getSub(i);
    sub[x] += shift(sub[i]);
  }
}

void getRoot(int x) {
  for (int i : edge[x]) {
    root[i] = sub[i] + shift(root[x] - shift(sub[i]));
    getRoot(i);
  }
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int m;
  cin >> m;
  for (int t = 1; t <= m; t++) {
    int n, rt = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      int fa;
      cin >> fa;
      if (fa) {
        edge[fa].push_back(i);
      } else {
        rt = i;
      }
    }
    getSub(rt);
    root[rt] = sub[rt];
    getRoot(rt);
    ull hash = 1;
    for (int i = 1; i <= n; i++) {
      hash += shift(root[i]);
    }
    if (!trees.count(hash)) {
      trees[hash] = t;
    }
    cout << trees[hash] << '\n';
    for (int i = 1; i <= n; i++) {
      edge[i].clear();
    }
  }
}

Method 2

#include <iostream>
#include <map>
#include <random>
#include <vector>

using ull = unsigned long long;
using Hash2 = std::pair<ull, ull>;

constexpr int N = 60, M = 998244353;
const ull mask = std::mt19937_64(time(nullptr))();

ull shift(ull x) {
  x ^= mask;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  x ^= mask;
  return x;
}

int n;
int size[N], weight[N], centroid[2];
std::vector<int> edge[N];
std::map<Hash2, int> trees;

void getCentroid(int x, int fa) {
  size[x] = 1;
  weight[x] = 0;
  for (int i : edge[x]) {
    if (i == fa) {
      continue;
    }
    getCentroid(i, x);
    size[x] += size[i];
    weight[x] = std::max(weight[x], size[i]);
  }
  weight[x] = std::max(weight[x], n - size[x]);
  if (weight[x] <= n / 2) {
    int index = centroid[0] != 0;
    centroid[index] = x;
  }
}

ull getHash(int x, int fa) {
  ull hash = 1;
  for (int i : edge[x]) {
    if (i == fa) {
      continue;
    }
    hash += shift(getHash(i, x));
  }
  return hash;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int m;
  cin >> m;
  for (int t = 1; t <= m; t++) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      int fa;
      cin >> fa;
      if (fa) {
        edge[fa].push_back(i);
        edge[i].push_back(fa);
      }
    }
    getCentroid(1, 0);
    Hash2 hash;
    hash.first = getHash(centroid[0], 0);
    if (centroid[1]) {
      hash.second = getHash(centroid[1], 0);
      if (hash.first > hash.second) {
        std::swap(hash.first, hash.second);
      }
    } else {
      hash.second = hash.first;
    }
    if (!trees.count(hash)) {
      trees[hash] = t;
    }
    cout << trees[hash] << '\n';
    for (int i = 1; i <= n; i++) {
      edge[i].clear();
    }
    centroid[0] = centroid[1] = 0;
  }
}

HDU 6647 Bracket Sequences on Tree

The problem asks for the number of essentially different bracket sequences produced by traversing an unrooted tree.

First observe that two non-isomorphic rooted trees cannot produce the same bracket sequence. Consider the number of essentially different bracket sequences produced when traversing a rooted tree. For the subtree currently rooted at $u$ , let $f(u)$ be its number of sequences. Starting from $u$ , the children may be visited in any order, producing $|son(u)|!$ permutations. For each child $v$ , the subtree of $v$ contributes $f(v)$ possibilities, so $f(u)=|son(u)|! \cdot \prod_{v \in son(u)} f(v)$ . However, isomorphic subtrees produce duplicates, so $f(u)$ must be divided by the product of the factorials of the occurrence counts of each essentially different subtree, just as for permutations of a multiset.

The DP above computes the number of possibilities for the root. Then rerooting DP transfers the hash and possibility information from a parent to its children, allowing us to compute the hash and number of possibilities for every choice of root. Each distinct subtree only needs to be counted once.

Reference implementation

#include <iostream>
#include <map>
#include <random>
#include <vector>

using ull = unsigned long long;

constexpr int N = 1e5 + 10, M = 998244353;
const ull mask = std::mt19937_64(time(nullptr))();

struct Tree {
  ull hash, deg, ans;
  std::map<ull, ull> son;

  Tree() { clear(); }

  void add(Tree& o);
  void remove(Tree& o);
  void clear();
};

ull inv(ull x) {
  ull y = M - 2, z = 1;
  while (y) {
    if (y & 1) {
      z = z * x % M;
    }
    x = x * x % M;
    y >>= 1;
  }
  return z;
}

ull shift(ull x) {
  x ^= mask;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  x ^= mask;
  return x;
}

void Tree::add(Tree& o) {
  ull temp = shift(o.hash);
  hash += temp;
  ans = ans * ++deg % M * inv(++son[temp]) % M * o.ans % M;
}

void Tree::remove(Tree& o) {
  ull temp = shift(o.hash);
  hash -= temp;
  ans = ans * inv(deg--) % M * son[temp]-- % M * inv(o.ans) % M;
}

void Tree::clear() {
  hash = 1;
  deg = 0;
  ans = 1;
  son.clear();
}

std::vector<int> edge[N];
Tree sub[N], root[N];
std::map<ull, ull> trees;

void getSub(int x, int fa) {
  for (int i : edge[x]) {
    if (i == fa) {
      continue;
    }
    getSub(i, x);
    sub[x].add(sub[i]);
  }
}

void getRoot(int x, int fa) {
  for (int i : edge[x]) {
    if (i == fa) {
      continue;
    }
    root[x].remove(sub[i]);
    root[i] = sub[i];
    root[i].add(root[x]);
    root[x].add(sub[i]);
    getRoot(i, x);
  }
  trees[root[x].hash] = root[x].ans;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t, n;
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 1; i < n; i++) {
      int u, v;
      cin >> u >> v;
      edge[u].push_back(v);
      edge[v].push_back(u);
    }
    getSub(1, 0);
    root[1] = sub[1];
    getRoot(1, 0);
    ull tot = 0;
    for (auto p : trees) {
      tot = (tot + p.second) % M;
    }
    cout << tot << '\n';
    for (int i = 1; i <= n; i++) {
      edge[i].clear();
      sub[i].clear();
      root[i].clear();
    }
    trees.clear();
  }
}

References

The hashing method in this article is based on and extends the blog post An Easy-to-Write Tree Hash That Cannot Be Defeated.