PQ Tree

A PQ tree is a tree-based data structure that represents a family of permutations of a set of elements. It was discovered and named by Kellogg S. Booth and George S. Lueker in 1976 to solve the following problem:

Given $m$ sets $S_i$, find a permutation of $1\sim n$ such that the elements in every set are consecutive.

A PQ tree can be constructed in $O(n+\sum|S_i|)$ time. The construction method introduced in this article has time complexity $O(nm)$.

Definition

A PQ tree has three types of nodes: leaf nodes, P nodes, and Q nodes. A leaf node represents an element in the permutation, a P node means that its children may be arranged in any order, and a Q node means that the order of its children may be reversed. Every non-leaf node is either a P node or a Q node. A P node has at least 2 children, and a Q node has at least 3 children.
By definition, a PQ tree itself represents all valid solutions, and its preorder traversal is one of them.
The figure below shows a PQ tree.

Its preorder traversal, 1,2,3,4,5, represents one valid solution. If the children of the P node are rearranged as 4,2,3, we obtain another valid solution, 1,4,2,3,5. Keeping the order of the P node's children unchanged and reversing the order of the Q node's children gives another valid solution, 5,3,2,4,1.

Construction

PQ trees use the child-sibling representation.

We construct a PQ tree incrementally.

First, build a tree whose root is a P node with $n$ children, namely $1,2,\ldots,n$, representing the PQ tree when there are no restrictions. As restrictions are added, we repeatedly modify this tree.

When a new restriction set $S$ is added, mark every leaf node belonging to this set black, and every leaf node not in this set white. For every non-leaf node, mark it black if all of its children are black, white if all of its children are white, and gray otherwise. In the figure below, black, white, and gray nodes are represented by black, gray, and half black/half gray, respectively.

We require the nodes in the PQ tree to be ordered by color.

Bottom-Up Method

The smallest subtree containing all black nodes is called the pertinent subtree, and the root of the pertinent subtree (which is not necessarily the root of the whole tree) is called the pertinent root.

The process of adding a restriction is called a reduction. A reduction has two phases: the bubbling phase and the reduction phase.

Bubbling Phase

The bubbling phase processes only the pertinent subtree. We mark every node in the pertinent subtree black or gray, and calculate the number of pertinent children of each node. To do this efficiently, we process the pertinent subtree from the leaves toward the root. This requires recording the parent of each node, but a node's parent is often modified during the reduction phase. To construct the tree in linear time, only the children of P nodes and the last child of a Q node always have their correct parent recorded. For the other children of a Q node, their parents are updated during the bubbling phase using the parent of the last child.

When we encounter an intermediate node, we check whether its sibling already has a valid parent. If not, we mark it as blocked. If its sibling later obtains a valid parent, we update this node's parent and remove the mark. If a consecutive block of blocked nodes remains when the bubbling phase ends (as in Q3 below), a parentless pseudo-node becomes the parent of that block and is removed during the reduction phase.

Reduction Phase

The reduction phase processes nodes with a queue. First, add all leaf nodes in the restriction to the queue. Each time, remove the node $u$ at the head of the queue and process it. If the parent of $u$ is also a node in the pertinent subtree, add $\mathit{fa}_u$ to the queue.
For each node $u$, we discuss the possible cases. If none of them applies, there is no solution.

Leaf Nodes

Mark $u$ black.

P Nodes

If all children are black, mark $u$ black.

If $u$ has both black and white children and $u$ is the pertinent root, create a new P node $v$ as the root of all its black children.

If $u$ has both black and white children and $u$ is not the pertinent root, perform the following operations:

• Create a new P node $f$ as the root of all black children.
• Create a new P node $e$ as the root of all white children.
• If $e$ (and/or $f$) has only one child, do not create a new node; assign $e$ (and/or $f$) directly to that child instead.
• Change $u$ into a Q node, set its children to $e$ and $f$, and mark it gray.

According to the definition above, a Q node must have at least 3 children, so $u$ is regarded as a pseudo-node here and will continue to be processed later.

If $u$ has one gray child $p$ and $u$ is the pertinent root, create a new P node $v$ as the root of all its black children, set $v$'s sibling to the last black child of $p$, and then set $v$ as the last child of $p$.

If $u$ has one gray child $p$ and $u$ is not the pertinent root, perform the following operations:

• Create a new P node $f$ as the root of all black children.
• Create a new P node $e$ as the root of all white children.
• If $e$ (and/or $f$) has only one child, do not create a new node; assign $e$ (and/or $f$) directly to that child instead.
• Set $e$'s sibling to the last white child of $p$, and then set $e$ as the last child of $p$.
• Set $f$'s sibling to the last black child of $p$, and then set $f$ as the last child of $p$.

If $u$ has exactly two gray children $p_1,p_2$, perform the following operations:

• Create a new P node $f$ as the root of all black children.
• If $f$ has only one child, do not create a new node; assign $f$ directly to that child instead.
• Set the sibling of the last black child of $p_1$ to $f$.
• Set $f$'s sibling to the last black child of $p_2$.
• Set the last child of $p_2$ to the last white child of $p_2$.

It can be seen that this merges $p_2$ into $p_1$.

Q Nodes

If $u$ has only black children, mark $u$ black. (The shape in the figure below is wrong.)

If $u$ has one gray child $p$, and all children with the same mark occur consecutively, perform the following operations:

• Let $p_f$ be the last black child of $p$, $p_e$ the last white child of $p$, $f$ the black sibling of $p$, and $e$ the white sibling of $p$.
• Set $f$'s sibling to $p_f$ and $e$'s sibling to $p_e$.
• If $p$ has no white sibling or black sibling, set the last child of $u$ to the last child of $p$.
• Delete $p$.

If $u$ has exactly two gray children $p_1,p_2$, and all children with the same mark occur consecutively, apply the preceding operation to $p_1,p_2$.

This construction method is from the original paper, but it is inconvenient to implement.

Top-Down Method

Most OI implementations use this method. The idea is similar; most of the cases below can also be found above.

Notice that, according to the coloring process described earlier, all black and white nodes already satisfy the conditions, so we only need to process gray nodes.

P Nodes

• If $u$ has more than two gray children, there is no solution.
• If $u$ has exactly one gray child and no black children, recursively process the gray child.
• Otherwise, first clear the children of $u$, then add all white children. Create a new Q node $q_1$ and make it a child of $u$. Add all gray children to $q_1$. Create a new P node $p$ as the root of all black children, and insert $p$ in the middle of $q_1$. (This corresponds to all cases for P nodes in the bottom-up method.)

Notice that we require the white parts of the two gray nodes to be entirely on the left and the black parts entirely on the right (or vice versa). Therefore, we need to implement a split function, split, that can divide the nodes of this subtree into black and white parts while preserving all possible resulting subtrees.

Q Nodes

• Find the positions $l,r$ of the leftmost and rightmost non-white nodes. If there is a non-black node in $[l+1,r-1]$, there is no solution.
• If there are no black nodes and there is only one gray node, recursively process this gray node; otherwise, it is only necessary to split the nodes at positions $l$ and $r$.

Split Function

Let the node to be split be $u$. We want to split $u$ into a forest with only white nodes on the left and only black nodes on the right. If $u$ is not a gray node, return the subtree directly. Only consider the gray-node case. If $u$ is a P-type node:

• If $u$ has at least two gray children, there is no solution.
• Otherwise, the left side consists of all white children, the middle recursively processes the gray child, and the right side consists of all black children. Note that all possibilities must be preserved, so create two new P nodes as the roots of the white children and the black children, respectively. (This corresponds to case P4 of the bottom-up method.)
• Delete $u$.

If $u$ is a Q-type node:

• If neither the forward nor the reverse order satisfies white-gray-black, there is no solution.
• If there are at least two gray children, there is no solution.
• Otherwise, recursively split the gray child.
• Delete $u$.

Finally, delete all redundant nodes (nodes with only one child).

Implementation

class PQTree {
 public:
  PQTree() {}

  void Init(int n) {
    n_ = n, rt_ = tot_ = n + 1;
    for (int i = 1; i <= n; i++) g_[rt_].emplace_back(i);
  }

  void Insert(const std::string &s) {
    s_ = s;
    Dfs0(rt_);
    Work(rt_);
    while (g_[rt_].size() == 1) rt_ = g_[rt_][0];
    Remove(rt_);
  }

  std::vector<int> ans() {
    DfsAns(rt_);
    return ans_;
  }

  ~PQTree() {}

 private:
  int n_, rt_, tot_, pool_[100001], top_, typ_[100001] /* 0-P 1-Q */,
      col_[100001] /* 0-black 1-white 2-grey */;
  std::vector<int> g_[100001], ans_;
  std::string s_;

  void Fail() {
    std::cout << "NO\n";
    std::exit(0);
  }

  int NewNode(int ty) {
    int x = top_ ? pool_[top_--] : ++tot_;
    typ_[x] = ty;
    return x;
  }

  void Delete(int u) { g_[u].clear(), pool_[++top_] = u; }

  void Dfs0(int u) {  // get color of each node
    if (u >= 1 && u <= n_) {
      col_[u] = s_[u] == '1';
      return;
    }
    bool c0 = false, c1 = false;
    for (auto &&v : g_[u]) {
      Dfs0(v);
      if (col_[v]) c1 = true;
      if (col_[v] != 1) c0 = true;
    }
    if (c0 && !c1)
      col_[u] = 0;
    else if (!c0 && c1)
      col_[u] = 1;
    else
      col_[u] = 2;
  }

  bool Check(const std::vector<int> &v) {
    int p2 = -1;
    for (int i = 0; i < static_cast<int>(v.size()); i++)
      if (col_[v[i]] == 2) {
        if (p2 != -1) return false;
        p2 = i;
      }
    if (p2 == -1)
      for (int i = 0; i < static_cast<int>(v.size()); i++)
        if (col_[v[i]]) {
          p2 = i;
          break;
        }
    for (int i = 0; i < p2; i++)
      if (col_[v[i]]) return false;
    for (int i = p2 + 1; i < static_cast<int>(v.size()); i++)
      if (col_[v[i]] != 1) return false;
    return true;
  }

  std::vector<int> Split(int u) {
    if (col_[u] != 2) return {u};
    std::vector<int> ng;
    if (typ_[u]) {  // Q
      if (!Check(g_[u])) {
        std::reverse(g_[u].begin(), g_[u].end());
        if (!Check(g_[u])) Fail();
      }
      for (auto &&v : g_[u])
        if (col_[v] != 2) {
          ng.emplace_back(v);
        } else {
          auto s = Split(v);
          ng.insert(ng.end(), s.begin(), s.end());
        }
    } else {  // P
      std::vector<int> son[3];
      for (auto &&x : g_[u]) son[col_[x]].emplace_back(x);
      if (son[2].size() > 1) Fail();
      if (!son[0].empty()) {
        int n0 = NewNode(0);
        g_[n0] = son[0];
        ng.emplace_back(n0);
      }
      if (!son[2].empty()) {
        auto s = Split(son[2][0]);
        ng.insert(ng.end(), s.begin(), s.end());
      }
      if (!son[1].empty()) {
        int n1 = NewNode(0);
        g_[n1] = son[1];
        ng.emplace_back(n1);
      }
    }
    Delete(u);
    return ng;
  }

  void Work(int u) {
    if (col_[u] != 2) return;
    if (typ_[u]) {  // Q
      int l = 1e9, r = -1e9;
      for (int i = 0; i < static_cast<int>(g_[u].size()); i++)
        if (col_[g_[u][i]]) checkmin(l, i), checkmax(r, i);
      for (int i = l + 1; i < r; i++)
        if (col_[g_[u][i]] != 1) Fail();
      if (l == r && col_[g_[u][l]] == 2) {
        Work(g_[u][l]);
        return;
      }
      std::vector<int> ng;
      for (int i = 0; i < l; i++) ng.emplace_back(g_[u][i]);
      auto s = Split(g_[u][l]);
      ng.insert(ng.end(), s.begin(), s.end());
      for (int i = l + 1; i < r; i++) ng.emplace_back(g_[u][i]);
      if (l != r) {
        s = Split(g_[u][r]);
        std::reverse(s.begin(), s.end());
        ng.insert(ng.end(), s.begin(), s.end());
      }
      for (int i = r + 1; i < static_cast<int>(g_[u].size()); i++)
        ng.emplace_back(g_[u][i]);
      g_[u] = ng;
    } else {  // P
      std::vector<int> son[3];
      for (auto &&x : g_[u]) son[col_[x]].emplace_back(x);
      if (son[1].empty() && son[2].size() == 1) {
        Work(son[2][0]);
        return;
      }
      g_[u].clear();
      if (son[2].size() > 2) Fail();
      g_[u] = son[0];
      int n1 = NewNode(1);
      g_[u].emplace_back(n1);
      if (son[2].size() >= 1) {
        auto s = Split(son[2][0]);
        g_[n1].insert(g_[n1].end(), s.begin(), s.end());
      }
      if (son[1].size()) {
        int n2 = NewNode(0);
        g_[n1].emplace_back(n2);
        g_[n2] = son[1];
      }
      if (son[2].size() >= 2) {
        auto s = Split(son[2][1]);
        std::reverse(s.begin(), s.end());
        g_[n1].insert(g_[n1].end(), s.begin(), s.end());
      }
    }
  }

  void Remove(int u) {  // remove the nodes with only one child
    for (auto &&v : g_[u]) {
      int tv = v;
      while (g_[tv].size() == 1) {
        int t = tv;
        tv = g_[tv][0];
        Delete(t);
      }
      v = tv, Remove(v);
    }
  }

  void DfsAns(int u) {
    if (u >= 1 && u <= n_) {
      ans_.emplace_back(u);
      return;
    }
    for (auto &&v : g_[u]) DfsAns(v);
  }
} T;

Exercises

• CF243E Matrix
• CF1552I Organizing a Music Festival

References

• Booth, Kellogg S. & Lueker, George S. (1976)."Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms".Journal of Computer and System Sciences.13(3): 335–379.doi:10.1016/S0022-0000(76)80045-1.
• PQ Tree Algorithm and Consecutive Ones Problem
• CF243E Matrix PQTree - RainAir's Blog