| 90 | |
| 91 | // 递归版 |
| 92 | public static void build1(int u, int fa) { |
| 93 | dep[u] = dep[fa] + 1; |
| 94 | dfn[u] = ++cntd; |
| 95 | siz[u] = 1; |
| 96 | stjump[u][0] = fa; |
| 97 | stout[u][0] = ++cntt; |
| 98 | addEdge2(startTag[u], cntt); |
| 99 | addEdge2(startTag[fa], cntt); |
| 100 | stin[u][0] = ++cntt; |
| 101 | addEdge2(cntt, endTag[u]); |
| 102 | addEdge2(cntt, endTag[fa]); |
| 103 | for (int p = 1; p < MAXP; p++) { |
| 104 | stjump[u][p] = stjump[stjump[u][p - 1]][p - 1]; |
| 105 | stout[u][p] = ++cntt; |
| 106 | addEdge2(stout[u][p - 1], cntt); |
| 107 | addEdge2(stout[stjump[u][p - 1]][p - 1], cntt); |
| 108 | stin[u][p] = ++cntt; |
| 109 | addEdge2(cntt, stin[u][p - 1]); |
| 110 | addEdge2(cntt, stin[stjump[u][p - 1]][p - 1]); |
| 111 | } |
| 112 | for (int e = head1[u]; e > 0; e = next1[e]) { |
| 113 | int v = to1[e]; |
| 114 | if (v != fa) { |
| 115 | build1(v, u); |
| 116 | siz[u] += siz[v]; |
| 117 | } |
| 118 | } |
| 119 | } |
| 120 | |
| 121 | // 迭代版 |
| 122 | public static void build2(int cur, int father) { |