(int cur, int tag)
| 191 | |
| 192 | // dfs2改成迭代版 |
| 193 | public static void dfs4(int cur, int tag) { |
| 194 | stacksize = 0; |
| 195 | push(cur, 0, tag, -1); |
| 196 | while (stacksize > 0) { |
| 197 | pop(); |
| 198 | if (e == -1) { |
| 199 | top[u] = t; |
| 200 | if (son[u] == 0) { |
| 201 | continue; |
| 202 | } |
| 203 | push(u, 0, t, -2); |
| 204 | push(son[u], 0, t, -1); |
| 205 | continue; |
| 206 | } else if (e == -2) { |
| 207 | e = head[u]; |
| 208 | } else { |
| 209 | e = nxt[e]; |
| 210 | } |
| 211 | if (e != 0) { |
| 212 | push(u, 0, t, e); |
| 213 | int v = to[e]; |
| 214 | if (v != fa[u] && v != son[u]) { |
| 215 | push(v, 0, v, -1); |
| 216 | } |
| 217 | } |
| 218 | } |
| 219 | } |
| 220 | |
| 221 | // 找重心需要计算子树大小的递归版，java会爆栈，C++不会 |
| 222 | public static void getSize1(int u, int fa) { |