Skip to content

PQ Tree

A PQ tree is a tree-based data structure that represents a set of permutations over a group 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 all elements within each set are consecutive.

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

Definition

A PQ tree has three types of nodes: leaf nodes, P-nodes, and Q-nodes. Leaf nodes represent elements in the permutation. A P-node indicates that its children can be arranged in any order, while a Q-node indicates that the order of its children can be reversed. All non-leaf nodes are either P-nodes or Q-nodes. A P-node has at least 2 children, and a Q-node has at least 3 children.
Due to the node definitions, the PQ tree itself represents all valid solutions, and its preorder traversal yields one of them.
The following figure shows a PQ tree.

Its preorder traversal 1,2,3,4,5 represents a valid solution. If the children of the P-node are rearranged to 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 yields 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 with a P-node as the root and \(n\) children, namely \(1,2,\ldots,n\), representing the PQ tree with no constraints. As constraints are added one by one, we continuously modify this tree.

When adding a new constraint set \(S\), we mark all leaf nodes belonging to this set as black, and leaf nodes not in this set as white. For all non-leaf nodes, if all their children are black, mark them as black; if all their children are white, mark them as white; otherwise, mark them as gray. In the diagrams below, black, white, and gray nodes are represented by black, gray, and half-black-half-gray colors, respectively.

We require that nodes in the PQ tree be sorted by color.

Bottom-Up Method

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

The process of adding a constraint is called a reduction. A reduction consists of two phases: the bubble phase and the reduce phase.

Bubble Phase

The bubble phase only processes the pertinent subtree. We mark all nodes in the pertinent subtree as black or gray and compute the number of pertinent children for each node. To do this efficiently, we process the pertinent subtree from leaves to the root. This requires recording the parent of each node, but during the reduce phase, a node's parent often needs to be modified. To construct in linear time, only the children of P-nodes and the last child of a Q-node always have their correct parent recorded. For other children of a Q-node, their parent is updated during the bubble phase using the parent of the last child.

When encountering an intermediate node, we check whether its sibling already has a valid parent. If not, mark it as blocked. If its sibling later obtains a valid parent, update this node's parent and remove the mark. If at the end of the bubble phase, there is still a contiguous block of blocked nodes (as in case Q3 below), a "pseudo-node" without a parent becomes the parent of that block and is removed during the reduce phase.

Reduce Phase

The reduce phase processes nodes using a queue. First, enqueue all leaf nodes within the constraint. Each time, dequeue the front node \(u\) and process it. If \(u\)'s parent is also in the pertinent subtree, enqueue \(\mathit{fa}_u\).
For each node \(u\), we discuss cases. If it does not belong to any of these cases, there is no solution.

Leaf Node

Mark \(u\) as black.

P-Node

If all children are black, mark \(u\) as 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; instead, assign \(e\) (and/or \(f\)) directly to that child.
  • Change \(u\) to a Q-node, set its children as \(e\) and \(f\), and mark it as gray.

Note that according to the earlier definition, a Q-node has at least 3 children, so \(u\) here is treated as a "pseudo-node" and will be processed further later.

If \(u\) has a 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 as the last black child of \(p\), and then set \(v\) as the last child of \(p\).

If \(u\) has a 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; instead, assign \(e\) (and/or \(f\)) directly to that child.
  • Set \(e\)'s sibling as the last white child of \(p\), and then set \(e\) as the last child of \(p\).
  • Set \(f\)'s sibling as 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; instead, assign \(f\) directly to that child.
  • Set the sibling of the last black child of \(p_1\) as \(f\).
  • Set the sibling of \(f\) as the last black child of \(p_2\).
  • Set the last child of \(p_2\) as the last white child of \(p_2\).

It can be seen that \(p_2\) is thus merged into \(p_1\).

Q-Node

If \(u\) has only black children, mark \(u\) as black. (The shape in the diagram below is incorrect.)

If \(u\) has a gray child \(p\), and all children with the same mark appear consecutively, perform the following operations:

  • Let \(p_f\) be the last black child of \(p\), \(p_e\) be the last white child of \(p\), \(f\) be the black sibling of \(p\), and \(e\) be the white sibling of \(p\).
  • Set the sibling of \(f\) as \(p_f\), and the sibling of \(e\) as \(p_e\).
  • If \(p\) does not have a white sibling or a black sibling, set the last child of \(u\) as 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 appear consecutively, perform the above operation on both \(p_1\) and \(p_2\).

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

Top-Down Method

Most implementations in OI currently use this method. The approach is similar, and the cases below can mostly be found above.

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

P-Node

  • If \(u\) has more than two gray children, there is no solution.
  • If \(u\) has only one gray child and no black children, recursively process the gray child.
  • Otherwise, first clear \(u\)'s children, 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\) into the middle of \(q_1\). (This corresponds to all cases of P-nodes in the bottom-up method.)

Note that we require the two gray nodes to have all whites on the left and all blacks on the right (or vice versa), so we need to implement a split function split that can split the subtree's nodes into white and black parts while preserving all possibilities of the resulting subtrees' nodes.

Q-Node

  • Find the leftmost and rightmost non-white node positions \(l,r\). If there are non-black nodes within \([l+1,r-1]\), there is no solution.
  • If there are no black nodes and only one gray node, recursively process this gray node; otherwise, only need to split the nodes at positions \(l\) and \(r\).

Split Function

Let the node to split be \(u\). We want to split \(u\) into a forest where the left side is all white and the right side is all black. If \(u\) is not a gray node, directly return the subtree. Only consider the case where \(u\) is a gray node.

If \(u\) is a P-node:

  • If \(u\) has at least two gray children, there is no solution.
  • Otherwise, the left side consists of all white children, the middle is the recursively processed gray child, and the right side consists of all black children. Note that to preserve all possibilities, we need to create two new P-nodes as the roots of the white and black children, respectively. (Corresponds to case P4 in the bottom-up method.)
  • Delete \(u\).

If \(u\) is a Q-node:

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

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

Code Implementation

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
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

References

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用