int dfs(int v, int p, int c);

int dfs1(int v, int p, int c) {
    if (tm[v]) {
        dfs(v, -1, 0);
        return 1;
    }
    int t;
    for (int &u : g[v])
        if (nr[u] == nr[v])
            t = dfs1(u, v, c + 1), dp[v] += dp[u];
    for (int& u : g[v]) {
        if (nr[u] != -1 && nr[u] != nr[v])
            dfs1(u, -1, min(t, c)), dp[v] += dp[u];
    }
    return t + 1;
}

int dfs(int v = 0, int p = -1, int c = 0) {
    if (p != -1 && sz(g[v]) == 1) {
        dp[v] = 0;
        return 1;
    }
    int t = 1e10;
    if (tm[v])
        t = 0;
    for (int& u : g[v]) {
        if (nr[u] == -1)
            continue;
        dfs1(u, -1, t);
        dp[v] += dp[u];
    }
    return t + 1;
}