自动搬运

查看原文

来自洛谷，原作者为

	灵乌路空 已退役 | 东方众OIer交流群 (幻想乡养老院) : 691090556

搬运于2025-08-24 21:45:52，当前版本为作者最后更新于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$ :

  • 初始化:
    $f[i][1]=1\ ,\ f[i][0]=1$,
    代表将每个点 ， 染成某种颜色的代价均为 $1$

    特别的 , 对于叶节点 , $f[i][\ (!c[i])\ ] = INF$ , $(\ c[i]$ 为叶节点应该变成的颜色 $)$ ,
    表示叶节点 $i$ 不应被染成其他颜色,
    所以设为极大代价 , 保证不会被用来更新其他节点

  之后 , 随意选择一个非叶节点 , 作为树根 , 开始进行 $DFS$

  1. 当到达叶节点时 ,
     直接 $return ;$ (叶节点的代价不需要被更新)
  2. 否则 , 循环枚举所有 非父亲节点 ,
     先更新它们的值
  3. 待递归回到 某节点时 ,
     用它已经被更新的子节点 ,
     来更新它的值

  $DFS$ 完成后 , 得到了所有的 $f[][]$ 的值 .
  由于根节点有 $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]));//取较小的值 
}