当你打反转左右儿子的标记时，不要这样：

void reverse(int p) {
  if (!p) return;
  tr[p].rev = true; // wrong
  swap(tr[p].son[0], tr[p].son[1]);
}

而是:

void reverse(int p) {
  if (!p) return;
  tr[p].rev ^= 1; // correct
  swap(tr[p].son[0], tr[p].son[1]);
}