| 128 | |
| 129 | // dfs2的迭代版 |
| 130 | public static void dfs4() { |
| 131 | stacksize = 0; |
| 132 | push(root, root, -1); |
| 133 | while (stacksize > 0) { |
| 134 | pop(); |
| 135 | if (edge == -1) { // edge == -1，表示第一次来到当前节点，并且先处理重儿子 |
| 136 | top[first] = second; |
| 137 | if (son[first] == 0) { |
| 138 | continue; |
| 139 | } |
| 140 | push(first, second, -2); |
| 141 | push(son[first], second, -1); |
| 142 | continue; |
| 143 | } else if (edge == -2) { // edge == -2，表示处理完当前节点的重儿子，回到了当前节点 |
| 144 | edge = head[first]; |
| 145 | } else { // edge >= 0, 继续处理其他的边 |
| 146 | edge = next[edge]; |
| 147 | } |
| 148 | if (edge != 0) { |
| 149 | push(first, second, edge); |
| 150 | if (to[edge] != fa[first] && to[edge] != son[first]) { |
| 151 | push(to[edge], to[edge], -1); |
| 152 | } |
| 153 | } |
| 154 | } |
| 155 | } |
| 156 | |
| 157 | public static int lca(int a, int b) { |
| 158 | while (top[a] != top[b]) { |