非常牛 dsu on tree

轩辕 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();
    }
}