题解 P3155 【[CQOI2009]叶子的染色】

灵乌路空 · 2019-07-15 16:46:28 · 题解

先无良宣传一下博客 wwwwww
文章列表 - 核融合炉心 - 洛谷博客

知识点: 树形DP , DFS

分析题意:

易证 , 随意选择一个不为叶节点的点为根
对答案没有任何影响
- 证明:由题,
  着色方案应该保证根结点到每个叶子的简单路径上
  都至少包含一个有色结点（哪怕是这个叶子本身）
  叶节点的着色方案
  只与其上方第一个有色节点有关
  由此,得证.
由上 , 假设随意选择了一个非叶节点 , 作为根节点:
并且 , 设f[i][j] ,为第 i 个点 , 将其染成 j 颜色,所需要的代价
- 可以得知,
  如果某一个节点需要被染成 x 色 ,
  并且他的父亲节点已经被染成了 x 色
  则,他不需要被染色 , 就可以继承父亲的颜色
- 则,对于某一个节点,
  其被染成 x 色的代价,
  1. 可以直接继承其父亲被染成 x 色的代价
  2. 可以保持父亲为非 x 色,
    并将此节点单独染成 x 色
可得到状态转移方程:
```
f[u][0]+=min(f[v][0]-1,f[v][1]); //u表示v的父亲节点   
f[u][1]+=min(f[v][1]-1,f[v][0]);
```
表示 , 将一个节点染成颜色 j 的代价 ,
即: 为其所有子节点染成颜色 j 代价的和 .

算法实现 :

由此 , 可以进行树形 DP :
- 初始化:
  代表将每个点，染成某种颜色的代价均为 $1
  特别的 , 对于叶节点 , f[i][\ (!c[i])\ ] = INF , (\ c[i] 为叶节点应该变成的颜色 ) ,
  表示叶节点 i 不应被染成其他颜色,
  所以设为极大代价 , 保证不会被用来更新其他节点
之后 , 随意选择一个非叶节点 , 作为树根 , 开始进行 DFS
1. 当到达叶节点时 ,
  直接 return ; (叶节点的代价不需要被更新)
2. 否则 , 循环枚举所有 非父亲节点 ,
  先更新它们的值
3. 待递归回到某节点时 ,
  用它已经被更新的子节点 ,
  来更新它的值
由于根节点有 $0,1$ 两种颜色的情况所以在根节点的两值 $f[root][0]$ 与 $f[root][1]$ 中 , 取一个最小值即所求的答案.

上代码 ~~(没必要那么多注释了吧)~~ :

#include<cstdio>
#include<queue>
#include<ctype.h>
#define int long long
#define min(a,b) a<b?a:b
//======================================================
const int MARX = 1e4+10;
const int INF = 2147483647;//极大值 
struct edge 
{
    int u,v,ne;
}e[2*MARX];
int m,n,c[MARX];//输入数据 
int root,num,head[MARX]; //建树 
int f[MARX][2]; // f[i][j]表示,第i个点,将其染成j颜色,所需要的代价
//======================================================
inline int read()
{
    int fl=1,w=0;char ch=getchar();
    while(!isdigit(ch) && ch!='-') ch=getchar();
    if(ch=='-') fl=-1;
    while(isdigit(ch)){w=w*10+ch-'0',ch=getchar();}
    return fl*w;
}
inline void add(int u,int v)
{
    e[++num].u=u,e[num].v=v;
    e[num].ne=head[u],head[u]=num;
}
void dfs(int u,int fa)
{
    if(u<=n) return ;//叶节点,直接return ; 
    for(int i=head[u],v=e[i].v;i;i=e[i].ne,v=e[i].v)//枚举所有非父节点 
      if(v!=fa)
      {
        dfs(v,u);
        f[u][0]+=min(f[v][0]-1,f[v][1]);//用子节点,更新当前点的各值 
        f[u][1]+=min(f[v][1]-1,f[v][0]);
      }
}
//======================================================
signed main()
{
    m=read(),n=read();
    root=n+1;//随意选择一个不为叶节点的节点 
    for(int i=1;i<=n;i++) c[i]=read();
    for(int i=1;i<=m-1;i++)
    {
      int u=read(),v=read();
      add(u,v),add(v,u);
    }
    for(int i=1;i<=m;i++)//初始化 
    {
      f[i][0]=f[i][1]=1;
      if(i<=n) f[i][(!c[i])]=INF;//叶节点特殊初始化 
    }
    dfs(root,root);
    printf("%lld",min(f[root][0],f[root][1]));//取较小的值 
}

题解 P3155 【[CQOI2009]叶子的染色】

知识点: 树形DP , DFS

分析题意:

算法实现 :