| 156 | } |
| 157 | |
| 158 | public static void calc(int u) { |
| 159 | getSize(u, 0); |
| 160 | cnte = 0; |
| 161 | for (int e = head[u]; e > 0; e = nxt[e]) { |
| 162 | int v = to[e]; |
| 163 | if (!vis[v]) { |
| 164 | edgeArr[++cnte][0] = e; |
| 165 | edgeArr[cnte][1] = siz[v]; |
| 166 | } |
| 167 | } |
| 168 | // 子树按大小或者高度排序，然后依次处理 |
| 169 | // 如果不按秩处理，建立窗口阶段，复杂度会炸 |
| 170 | // 课上会重点解释 |
| 171 | Arrays.sort(edgeArr, 1, cnte + 1, (a, b) -> a[1] - b[1]); |
| 172 | int l = 1, r = cntw, mid; |
| 173 | while (l <= r) { |
| 174 | mid = (l + r) >> 1; |
| 175 | if (check(u, mid)) { |
| 176 | l = mid + 1; |
| 177 | } else { |
| 178 | r = mid - 1; |
| 179 | } |
| 180 | if (r <= ans) { |
| 181 | break; |
| 182 | } |
| 183 | } |
| 184 | } |
| 185 | |
| 186 | public static void solve(int u) { |
| 187 | vis[u] = true; |