#樹形dp#jzoj 1010 洛谷 3155 葉子的顔色

題目

對于每個葉結點u，定義c[u]為從u到根結點的簡單路徑上第一個有色結點的顔色。給出每個c[u]的值，設計着色方案，使得着色結點的個數盡量少。

分析

這道題可以用樹形dp， f [ x ] [ 0 / 1 ] f[x][0/1] f[x][0/1]表示x點不着色/着色的最小着色結點個數，

容易得到 f [ x ] [ 0 ] = ∑ m i n ( f [ s o n ] [ 0 ] − 1 , f [ s o n ] [ 1 ] ) f[x][0]=\sum min(f[son][0]-1,f[son][1]) f[x][0]=∑min(f[son][0]−1,f[son][1])

f [ x ] [ 1 ] = ∑ m i n ( f [ s o n ] [ 0 ] , f [ s o n ] [ 1 ] − 1 ) f[x][1]=\sum min(f[son][0],f[son][1]-1) f[x][1]=∑min(f[son][0],f[son][1]−1)

初始化時，對于每個葉子節點着色為1，不着色inf，而根節點初始化都是1。

代碼

#include <cstdio>
#include <cctype>
#define min(a,b) (a<b)?a:b
using namespace std;
struct node{int y,next;}e[200001];
int n,m,ques[100001],ls[100001],f[200001][2];
int in(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
void dp(int x,int fa){
	if (x<=n) f[x][ques[x]]=1,f[x][ques[x]^1]=1<<23; else f[x][0]=f[x][1]=1;
	for (int i=ls[x];i;i=e[i].next){
		if (e[i].y==fa) continue;
		dp(e[i].y,x);
		f[x][0]+=min(f[e[i].y][0]-1,f[e[i].y][1]);
		f[x][1]+=min(f[e[i].y][0],f[e[i].y][1]-1);
	}
}
int main(){
	m=in(); n=in();
	for (int i=1;i<=n;i++) ques[i]=in();
	for (int i=1,x,y;i<m;i++){
		x=in(); y=in();
		e[i]=(node){y,ls[x]}; ls[x]=i;
		e[i+m]=(node){x,ls[y]}; ls[y]=i+m;
	}
	dp(m,0); return !printf("%d",min(f[m][0],f[m][1]));
}