D-嘻嘻嘻嘻嘻_一起来做题~欢乐赛7

题目描述

给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。对于每个叶结点u，定义c[u]为从根结点从U的简单路径上最后一个有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。

样例

算法1

(换根dp)

分析

先考虑有根的树形dp
每一个节点的状态只有三种染成白色，染成黑色，不染色
我们可以围绕这三个状态定义状态方程

状态表示状态计算

定义 $f[u][0/1/2]$ 再以u为根的子树中，将根节点 $u$ ,染成黑色(0)/ 染成白色(1)/ 不染色(2)的所有合法方案的方案中染色次数最少
状态计算：
1. 节点u染成黑色
  
  $f[u][0] =1 + \sum_v min(f[v][0] - 1,f[u][1],f[u][2])$
  
  解释：1：将u染成黑色的贡献， $f[v][0] - 1$ ：因为u已经染成黑色了所以v就不需要染成黑色了，把将v染成黑色的贡献去掉 -1
2. 将节点u染成白色
  
  $f[u][1] =1 + \sum_v min(f[v][0],f[u][1] - 1,f[u][2])$
  
  解释：1 ：将u染成白色的贡献， $f[v][0] - 1$ 因为u已经染成白色了所以v就不需要染成白色了，把将v染成白色的贡献去掉 -1
3. 节点u不染色
  
  $f[u][2] = \sum_v min(f[v][0],f[u][1],f[u][2])$

细节：

叶子节点需要特殊处理，设叶子节点为x
1. 当c[x] == 0时，叶子节点到根节点路径上第一个节点必须是黑色
  
  $f[x][0] = 1,f[x][1] = INF,f[x][2] = INF$
  
  解释： $f[x][0] = 1$ 显然叶子节点到根节点路径上第一个节点必须是黑色，那么将叶子节点染成黑色是合法的，贡献为1
  
  $f[x][1] = INF$ 显然叶子节点到根节点路径上第一个节点必须是黑色，那么将叶子节点染成白色是非法的，将它设为INF这样就不会更新答案
  
  $f[x][2] = INF$ , $f[x][2]$ 不染色合法是指以x为根的子树的所有叶子节点的 $c$ 都被除 $x$ 外的子节点满足了，叶子节点 $x$ 显然没有子节点能满足它所以是非法的，将它设为INF这样就不会更新答案
2. 当c[x] == 1时，叶子节点到根节点路径上第一个节点必须是白色
  
  $f[x][0] = INF,f[x][1] = 1,f[x][2] = INF$
  
  解释： $f[x][0] = INF$ 显然叶子节点到根节点路径上第一个节点必须是白色，那么将叶子节点染成黑色是非法的，将它设为INF这样就不会更新答案
  
  $f[x][1] = 1$ 显然叶子节点到根节点路径上第一个节点必须是白色，那么将叶子节点染成白色是合法的，贡献为1
  
  $f[x][2] = INF$ , $f[x][2]$ 不染色合法是指以x为根的子树的所有叶子节点的 $c$ 都被除 $x$ 外的子节点满足了，叶子节点 $x$ 显然没有子节点能满足它所以是非法的，将它设为INF这样就不会更新答案

时间复杂度 $O(n)$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

#define x first
#define y second

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 100010;
const int INF = 0x3f3f3f3f;
int h[N],ne[N * 2],e[N * 2],idx;
int color[N];
int c[N];
int f[N][3];
int ans;
int n,m;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

void dfs1(int u,int father)
{
    if(u <= m)
    {
        f[u][0] = (c[u]==0)?1:INF,f[u][1] = (c[u] == 1)?1:INF,f[u][2] = INF;
    }else
    {
        f[u][0] = 1,f[u][1] = 1;
        for(int i = h[u];~i;i = ne[i])
        {
            int j = e[i];
            if(j == father) continue;
            dfs1(j,u);
            f[u][0] += min(min(f[j][0] - 1,f[j][1]),f[j][2]);
            f[u][1] += min(min(f[j][0],f[j][1] - 1),f[j][2]);
            f[u][2] += min(min(f[j][0],f[j][1]),f[j][2]);
        }
    }
}

void dfs2(int u,int father)
{
    if(u > m)
    {

        for(int i = h[u];~i;i = ne[i])
        {
            int j = e[i];
            if(j == father) continue;
            int t0,t1,t2;
            t0 = f[u][0] - min(min(f[j][0] - 1,f[j][1]),f[j][2]);
            t1 = f[u][1] - min(min(f[j][0],f[j][1] - 1),f[j][2]);
            t2 = f[u][2] - min(min(f[j][0],f[j][1]),f[j][2]);
            f[j][0] += min(min(t0 - 1,t1),t2);
            f[j][1] += min(min(t0,t1 - 1),t2);
            f[j][2] += min(min(t0,t1),t2);
            dfs2(j,u);
        }
        ans = min(ans,min(min(f[u][0],f[u][1]),f[u][2]));
    }
}

void solve()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) h[i] = -1;
    for(int i = 1;i <= m;i ++) scanf("%d",&c[i]);
    for(int i = 0;i < n - 1;i ++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    ans = INF;
    dfs1(m + 1,0);
    // cout << f[m + 1][2] << endl;
    dfs2(m + 1,0);
    printf("%lld\n",ans);
} 

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    // init(N - 1); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cin >> _;

    // scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}