轩辕 4721 年，彩笔@硒六爱吃硫，在某日的西艾斯批%你赛中花了两个小时切掉了 T1 和 T2。
随后看到 T3，心想：“这不是傻逼题吗，建下克鲁斯卡尔重构树然后瞎几把低批不就做完了吗。”
发现并不会低批。
思考了一个小时发现并不是沙比低批，而是地艾斯优盎吹。
@硒六爱吃硫 打完暴力。注意到还有 \(40\) min。
what should he/she do?
遗憾的，@硒六爱吃硫 早就忘了地艾斯优盎吹怎么写。最终只拿下 36pts 的高分。
int siz[400005], son[400005];
void dfs1(int x, int fa) {siz[x] = 1;for(int i = head[x]; i; i = e[i].nxt) {int y = e[i].to;if(y == fa) continue;dfs1(y, x);if(siz[son[x]] < siz[y]) son[x] = y;siz[x] += siz[y];}
}
vector<int> st, now;
// now 表示当前重子树正在做的节点集合
// st 用于统计一个轻儿子内的节点集合
void dfs2(int x, int fa, int flg) {// flg == -1 表示计算以 x 为根的子树内的节点集合// flg == 0 表示计算以 x 为根的子树的答案，并不保留答案// flg == 1 表示计算以 x 为根的子树的答案，保留答案if(flg != -1) for(int i = head[x]; i; i = e[i].nxt) if(e[i].to != fa && e[i].to != son[x]) dfs2(e[i].to, x, 0);if(flg != -1 && son[x]) dfs2(son[x], x, 1);if(flg != -1 && x <= n) now.push_back(x), //维护数据结构等;for(int i = head[x]; i; i = e[i].nxt) {int y = e[i].to;if((y == son[x] && flg != -1) || y == fa) continue;dfs2(y, x, -1);if(flg != -1) {for(int z : st) {//计算答案}for(int z : st) now.push_back(z), //维护数据结构等;st.clear();}}if(flg == -1 && x <= n) st.push_back(x);if(flg == 0) {for(int z : now) //清空数据结构;now.clear();}
}
