| 165 | |
| 166 | // 迭代版，圆方树建立深度表和倍增表 |
| 167 | public static void dfs2(int cur, int father) { |
| 168 | stacksize = 0; |
| 169 | push(cur, 0, father, -1); |
| 170 | while (stacksize > 0) { |
| 171 | pop(); |
| 172 | if (e == -1) { |
| 173 | dep[u] = dep[fa] + 1; |
| 174 | stjump[u][0] = fa; |
| 175 | for (int p = 1; p < MAXP; p++) { |
| 176 | stjump[u][p] = stjump[stjump[u][p - 1]][p - 1]; |
| 177 | } |
| 178 | e = head2[u]; |
| 179 | } else { |
| 180 | e = next2[e]; |
| 181 | } |
| 182 | if (e != 0) { |
| 183 | push(u, 0, fa, e); |
| 184 | if (to2[e] != fa) { |
| 185 | push(to2[e], 0, u, -1); |
| 186 | } |
| 187 | } |
| 188 | } |
| 189 | } |
| 190 | |
| 191 | // 圆方树上，x和y的最低公共祖先 |
| 192 | public static int getLca(int x, int y) { |