| 129 | } |
| 130 | |
| 131 | public static void dfs(int u, int fa) { |
| 132 | stjump[u][0] = fa; |
| 133 | for (int p = 1; p < MAXP; p++) { |
| 134 | stjump[u][p] = stjump[stjump[u][p - 1]][p - 1]; |
| 135 | } |
| 136 | for (int e = head[u]; e > 0; e = next[e]) { |
| 137 | dfs(to[e], u); |
| 138 | } |
| 139 | if (u <= n) { |
| 140 | leafsiz[u] = 1; |
| 141 | leafDfnMin[u] = ++cntd; |
| 142 | leafseg[cntd] = u; |
| 143 | } else { |
| 144 | leafsiz[u] = 0; |
| 145 | leafDfnMin[u] = n + 1; |
| 146 | } |
| 147 | for (int e = head[u]; e > 0; e = next[e]) { |
| 148 | leafsiz[u] += leafsiz[to[e]]; |
| 149 | leafDfnMin[u] = Math.min(leafDfnMin[u], leafDfnMin[to[e]]); |
| 150 | } |
| 151 | } |
| 152 | |
| 153 | // 可持久化线段树的build |
| 154 | public static int build(int l, int r) { |