大意就是用 vector 直接记录
- 无需显式建出叶向树，只需记录 fa。
- dis 每个中只用记录 dep 个值，常数比 map 等小。
- 但是从上向下不太好做，加点删点是比较好做的。
void getsz(int u, int lst = 0) {
mxsz[u] = 0; sz[u] = 1;
for (int v : G[u]) if (!vis[v] && v != lst) {
getsz(v, u);
cmax(mxsz[u], sz[v]);
sz[u] += sz[v];
}
cmax(mxsz[u], all - sz[u]);
if (mn > mxsz[u]) mn = mxsz[u], rt = u;
}
void getdis(int u, int d, int lst) {
dis[u].eb(d);
for (int v : G[u]) if (!vis[v] && v != lst) {
getdis(v, d + 1, u);
}
}
void build(int u) {
getsz(u);
cnt[u] = _cnt_begin; _cnt_begin += sz[u] + 1;//这是那道题的一个桶
getdis(u, 0, 0);
vis[u] = 1;
for (int v : G[u]) if (!vis[v]) {
mn = 1e9, all = sz[v], rt = -1;
getsz(v); fa[rt] = u;
build(rt);
}
}
练习题
标签：sz,getsz,int,分治,一种,vis,lst,mxsz,写法 From： https://www.cnblogs.com/SkyMaths/p/18528303