Visits: 466

ARC097F Monochrome Cat

题意

• 给定一棵 $n$ 个点的树，每个点要么是白色要么是黑色。
• 你可以从任何一个顶点出发，每秒执行下列操作中的一个：
  • 走到一个相邻的节点，反转到达的节点颜色。
  • 反转所在的节点颜色。
• 问至少需要多少秒可以使所有节点变黑。
• $n \le 10^5$。

题解

首先肯定先把纯黑的子树剪掉。

假设我们要求必须回到起点，则我们一定会走一条欧拉回路。

$d_i$ 为 $i$ 的度数，在只进行第一个操作的情况下，花费的时间为 $2n – 2$ 秒，同时点 $i$ 的颜色会反转 $d_i$ 次，因此总花费时间还要加上反转后颜色为白色的点数。

考虑不要求回到起点有什么变化，此时实际去掉的路径就是从终点到起点的这一条链，除了终点都少被反转了一次。

考虑只走一遍欧拉回路后两种颜色的点的贡献变化：

• 对于黑色的点，如果少翻转一次，这个点即为白色，还是需要额外花费一次操作，因此操作数不变。
• 对于白色的点，如果少翻转一次，这个点即为黑色，省掉了额外将其反转的操作，因此操作数减二。

由于叶子节点一定是黑色的，问题可以简单的转化为求出一条包含白色点最多的路径，那么求个直径即可，时间复杂度 $\mathcal O(n)$。

要注意特判 $n=1$ 的情况，此时叶子节点是白色的。

代码

const int N = 1e5 + 7;
int n, ans, d[N];
vi e[N];
char s[N];
bool a[N], c[N], b[N];

void dfs1(int x, int fa) {
    b[x] = c[x];
    for (int y : e[x])
        if (y != fa)
            dfs1(y, x), b[x] |= b[y];
    ans += b[x];
    if (!b[x]) a[fa] ^= 1;
}

void dfs2(int x, int fa) {
    d[x] = d[fa] + c[x];
    for (int y : e[x])
        if (b[y] && y != fa)
            dfs2(y, x);
}

int main() {
    rd(n);
    for (int i = 1, x, y; i < n; i++)
        rd(x, y), e[x].pb(y), e[y].pb(x), a[x] ^= 1, a[y] ^= 1;
    rds(s, n);
    int rt = 0;
    for (int i = 1; i <= n; i++) {
        c[i] = s[i] == 'W';
        if (s[i] == 'W') rt = i;
    }
    if (!rt) return prints("0"), 0;
    dfs1(rt, 0);
    ans = ans * 2 - 2;
    if (!ans) return prints("1"), 0;
    for (int i = 1; i <= n; i++)
        if (b[i]) ans += c[i] ^= a[i];
    dfs2(rt, 0);
    for (int i = 1; i <= n; i++)
        if (b[i] && d[i] > d[rt]) rt = i;
    d[rt] = 0, dfs2(rt, 0);
    for (int i = 1; i <= n; i++)
        if (b[i] && d[i] > d[rt]) rt = i;
    print(ans - d[rt] * 2);
    return 0;
}