| 149 | |
| 150 | // dfs2的迭代版 |
| 151 | public static void dfs4() { |
| 152 | stacksize = 0; |
| 153 | push(1, 1, -1); |
| 154 | while (stacksize > 0) { |
| 155 | pop(); |
| 156 | if (edge == -1) { |
| 157 | top[first] = second; |
| 158 | dfn[first] = ++cntd; |
| 159 | if (son[first] == 0) { |
| 160 | continue; |
| 161 | } |
| 162 | push(first, second, -2); |
| 163 | push(son[first], second, -1); |
| 164 | continue; |
| 165 | } else if (edge == -2) { |
| 166 | edge = head[first]; |
| 167 | } else { |
| 168 | edge = next[edge]; |
| 169 | } |
| 170 | if (edge != 0) { |
| 171 | push(first, second, edge); |
| 172 | if (to[edge] != fa[first] && to[edge] != son[first]) { |
| 173 | push(to[edge], to[edge], -1); |
| 174 | } |
| 175 | } |
| 176 | } |
| 177 | } |
| 178 | |
| 179 | public static void up(int i) { |
| 180 | max[i] = Math.max(max[i << 1], max[i << 1 | 1]); |