| 120 | |
| 121 | // 迭代版 |
| 122 | public static void build2(int cur, int father) { |
| 123 | stacksize = 0; |
| 124 | push(cur, father, -1); |
| 125 | while (stacksize > 0) { |
| 126 | pop(); |
| 127 | if (e == -1) { |
| 128 | dep[u] = dep[fa] + 1; |
| 129 | dfn[u] = ++cntd; |
| 130 | siz[u] = 1; |
| 131 | stjump[u][0] = fa; |
| 132 | stout[u][0] = ++cntt; |
| 133 | addEdge2(startTag[u], cntt); |
| 134 | addEdge2(startTag[fa], cntt); |
| 135 | stin[u][0] = ++cntt; |
| 136 | addEdge2(cntt, endTag[u]); |
| 137 | addEdge2(cntt, endTag[fa]); |
| 138 | for (int p = 1; p < MAXP; p++) { |
| 139 | stjump[u][p] = stjump[stjump[u][p - 1]][p - 1]; |
| 140 | stout[u][p] = ++cntt; |
| 141 | addEdge2(stout[u][p - 1], cntt); |
| 142 | addEdge2(stout[stjump[u][p - 1]][p - 1], cntt); |
| 143 | stin[u][p] = ++cntt; |
| 144 | addEdge2(cntt, stin[u][p - 1]); |
| 145 | addEdge2(cntt, stin[stjump[u][p - 1]][p - 1]); |
| 146 | } |
| 147 | e = head1[u]; |
| 148 | } else { |
| 149 | e = next1[e]; |
| 150 | } |
| 151 | if (e != 0) { |
| 152 | push(u, fa, e); |
| 153 | if (to1[e] != fa) { |
| 154 | push(to1[e], u, -1); |
| 155 | } |
| 156 | } else { |
| 157 | for (int ei = head1[u]; ei > 0; ei = next1[ei]) { |
| 158 | int v = to1[ei]; |
| 159 | if (v != fa) { |
| 160 | siz[u] += siz[v]; |
| 161 | } |
| 162 | } |
| 163 | } |
| 164 | } |
| 165 | } |
| 166 | |
| 167 | public static boolean isAncestor(int a, int b) { |
| 168 | return dfn[a] <= dfn[b] && dfn[b] < dfn[a] + siz[a]; |