dsu on tree

const int N = 2e5 + 5;
int n;

int dp[N];

vector<int> adj[N];
int siz[N], ms[N], p[N];

void init() {
    for (int i = 1; i <= n; i++) {
        siz[i] = ms[i] = p[i] = 0;
        adj[i].clear();
    }
}

void dfs1(int now, int fa) {
    siz[now] = 1;
    ms[now] = -1;
    p[now] = fa;
    for (auto t : adj[now]) {
        if (t == fa) continue;
        dfs1(t, now);
        siz[now] += siz[t];
        if (ms[now] == -1 || siz[t] > siz[ms[now]]) ms[now] = t;
    }
}

// 计算 v 的子树对 dp[u] 的贡献
void cal_ans(int u, int v, int now, int fa) {
  // do sth

    for (auto t : adj[now]) {
        if (t == fa) continue;
        cal_ans(u, v, t, now);
    }
}

// 将 v 的子树加入已知集合
void add(int u, int v, int now, int fa) {
  // do sth

    for (auto t : adj[now]) {
        if (t == fa) continue;
        add(u, v, t, now);
    }
}

void del(int now, int fa) {
  // do sth

    for (auto t : adj[now]) {
        if (t == fa) continue;
        del(t, now);
    }
}

void dfs(int now, int fa, bool keep) {
    for (auto t : adj[now]) {
        if (t == fa || t == ms[now]) continue;
        dfs(t, now, 0);
    }

    if (ms[now] != -1) {
        dfs(ms[now], now, 1);
    }

    // 考虑清楚 dp[now] 与 dp[t] 的关系是什么？求和还是取 max

    for (auto t : adj[now]) {
        if (t == fa || t == ms[now]) continue;
        cal_ans(now, t, t, now);
        add(now, t, t, now);
    }

    // 结算 now

    if (keep == 0) {
        del(now, fa);
    }
}