【题解】Atcoder ARC#97 F-Monochrome Cat

　　好zz啊我……(；д；)

　　首先我们可以删掉所有只有黑色节点的子树（一定不会遍历到），且注意到每一个点你一定只会经过一遍。然后又考虑如果起点和终点相同，那么总次数实际上已经固定了：就是遍历整棵树（每一条边都需要经过两次），以及各点需要的改变颜色的额外花费。这个是可以愉快地 \(O(n)\) 统计的。再想起点和终点不相同的情况呢？其实就是可以让一个节点到一个叶子节点所经过的次数减少一次。一个本来需要额外花费的点，现在少经过了一次，既少走了一条路，又少改了一次颜色；而本来不需要的点，少走的路和改变颜色的花费抵消。我们给他们赋予权值表示可以节省的时间，这让我们的问题转化为：如何找到一条权值最大的链，且链的端点中有一个是叶子结点？

　　我们dp一下，因为一条路径一定由一条经过了叶子节点的路径和一条不一定经过了叶子结点的路径组成，这样找出最大的就可以了。

#include <bits/stdc++.h>

using namespace std;

#define maxn 100005

#define INF 99999999

int n, root, Ans, ans, C[maxn], mark[maxn];

int degree[maxn], dp1[maxn], dp2[maxn];

int val[maxn];

int read()

{

    int x = , k = ;

    char c; c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

struct edge

{

    int cnp, to[maxn * ], last[maxn * ], head[maxn];

    edge() { cnp = ; }

    void add(int u, int v)

    {

        to[cnp] = v, last[cnp] = head[u], head[u] = cnp ++;

        to[cnp] = u, last[cnp] = head[v], head[v] = cnp ++;

    }

}E1;

void dfs(int u, int fa)

{

    mark[u] = C[u];

    for(int i = E1.head[u]; i; i = E1.last[i])

    {

        int v = E1.to[i];

        if(v == fa) continue;

        dfs(v, u);

        if(!mark[v]) ++ degree[u], ++ degree[v];

        mark[u] &= mark[v];

    }

}

void dfs2(int u, int fa)

{

    int mx1 = , mx2 = ; bool flag = ;

    Ans += degree[u];

    if((degree[u] + C[u]) & ) val[u] = ;

    else val[u] = , ++ Ans;

    for(int i = E1.head[u]; i; i = E1.last[i])

    {

        int v = E1.to[i];

        if(v == fa || mark[v]) continue;

        flag = ; dfs2(v, u);

        ans = max(ans, max(dp1[v] + mx2 + val[u], dp2[v] + mx1 + val[u]));

        mx1 = max(dp1[v], mx1), mx2 = max(dp2[v], mx2);

    }

    dp1[u] = mx1 + val[u], dp2[u] = flag ? mx2 + val[u] : -INF;

}

int main()

{

    n = read();

    for(int i = ; i < n; i ++)

    {

        int x = read(), y = read();

        E1.add(x, y);

    }

    for(int i = ; i <= n; i ++)

    {

        char c; cin >> c;

        if(c == 'B') C[i] = ;

        else root = i;

    }

    if(!root) { puts(""); return ; }

    dfs(root, ); dfs2(root, );

    printf("%d\n", Ans - ans);

    return ;

}

巴特西

【题解】Atcoder ARC#97 F-Monochrome Cat

最新文章

热门文章