| 146 | |
| 147 | // dfs2的迭代版 |
| 148 | public static void dfs4() { |
| 149 | stacksize = 0; |
| 150 | push(1, 1, -1); |
| 151 | while (stacksize > 0) { |
| 152 | pop(); |
| 153 | if (edge == -1) { // edge == -1，表示第一次来到当前节点，并且先处理重儿子 |
| 154 | top[first] = second; |
| 155 | dfn[first] = ++cntd; |
| 156 | seg[cntd] = first; |
| 157 | if (son[first] == 0) { |
| 158 | continue; |
| 159 | } |
| 160 | push(first, second, -2); |
| 161 | push(son[first], second, -1); |
| 162 | continue; |
| 163 | } else if (edge == -2) { // edge == -2，表示处理完当前节点的重儿子，回到了当前节点 |
| 164 | edge = head[first]; |
| 165 | } else { // edge >= 0, 继续处理其他的边 |
| 166 | edge = next[edge]; |
| 167 | } |
| 168 | if (edge != 0) { |
| 169 | push(first, second, edge); |
| 170 | if (to[edge] != fa[first] && to[edge] != son[first]) { |
| 171 | push(to[edge], to[edge], -1); |
| 172 | } |
| 173 | } |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | public static void up(int i) { |
| 178 | int l = i << 1, r = i << 1 | 1; |