| 177 | |
| 178 | // dfs2是dfs1的迭代版 |
| 179 | public static void dfs2(int cur, int fa) { |
| 180 | stacksize = 0; |
| 181 | push(cur, fa, -1); |
| 182 | while (stacksize > 0) { |
| 183 | pop(); |
| 184 | if (e == -1) { |
| 185 | stjump[u][0] = f; |
| 186 | for (int p = 1; p < MAXP; p++) { |
| 187 | stjump[u][p] = stjump[stjump[u][p - 1]][p - 1]; |
| 188 | } |
| 189 | e = headk[u]; |
| 190 | } else { |
| 191 | e = nextk[e]; |
| 192 | } |
| 193 | if (e != 0) { |
| 194 | push(u, f, e); |
| 195 | push(tok[e], u, -1); |
| 196 | } else { |
| 197 | if (u <= n) { |
| 198 | mindist[u] = dist[u]; |
| 199 | } else { |
| 200 | mindist[u] = INF; |
| 201 | } |
| 202 | for (int ei = headk[u]; ei > 0; ei = nextk[ei]) { |
| 203 | mindist[u] = Math.min(mindist[u], mindist[tok[ei]]); |
| 204 | } |
| 205 | } |
| 206 | } |
| 207 | } |
| 208 | |
| 209 | public static int query(int node, int line) { |
| 210 | for (int p = MAXP - 1; p >= 0; p--) { |