你注意到线段树有:
struct Info { int cnt, lson, rson; } info[N * 22];
倍增有这么一段:
int anc[N][22];
发现这两个东西在不同时间段被用到。
那为什么不用 info[v * n + u].cnt 来代替一下 anc[u][v] 剩下一半的空间呢!
info[v * n + u].cnt
anc[u][v]
还要注意把 vector 都换掉。太占空间了。
vector