ARC097F Monochrome Cat 题解

作者: xht37 分类: 题解 发布时间: 2020-04-30 19:09

Visits: 366

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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注