(int u, int fa)
| 116 | } |
| 117 | |
| 118 | public static int getCentroid(int u, int fa) { |
| 119 | // getSize1(u, fa); |
| 120 | getSize2(u, fa); |
| 121 | int half = siz[u] >> 1; |
| 122 | boolean find = false; |
| 123 | while (!find) { |
| 124 | find = true; |
| 125 | for (int e = head[u]; e > 0; e = nxt[e]) { |
| 126 | int v = to[e]; |
| 127 | if (v != fa && !vis[v] && siz[v] > half) { |
| 128 | fa = u; |
| 129 | u = v; |
| 130 | find = false; |
| 131 | break; |
| 132 | } |
| 133 | } |
| 134 | } |
| 135 | return u; |
| 136 | } |
| 137 | |
| 138 | // 收集信息递归版，java会爆栈，C++可以通过 |
| 139 | public static void dfs1(int u, int fa, int dis, int edge) { |