| 193 | |
| 194 | // dfs2的迭代版 |
| 195 | public static void dfs4() { |
| 196 | stacksize = 0; |
| 197 | push(1, 1, -1); |
| 198 | while (stacksize > 0) { |
| 199 | pop(); |
| 200 | if (edge == -1) { |
| 201 | top[first] = second; |
| 202 | dfn[first] = ++cntd; |
| 203 | val[cntd] = arr[first]; |
| 204 | if (son[first] == 0) { |
| 205 | continue; |
| 206 | } |
| 207 | push(first, second, -2); |
| 208 | push(son[first], second, -1); |
| 209 | continue; |
| 210 | } else if (edge == -2) { |
| 211 | edge = head[first]; |
| 212 | } else { |
| 213 | edge = next[edge]; |
| 214 | } |
| 215 | if (edge != 0) { |
| 216 | push(first, second, edge); |
| 217 | if (to[edge] != fa[first] && to[edge] != son[first]) { |
| 218 | push(to[edge], to[edge], -1); |
| 219 | } |
| 220 | } |
| 221 | } |
| 222 | } |
| 223 | |
| 224 | public static void query(int l, int r) { |
| 225 | if (bi[l] == bi[r]) { |