Description
　　給一棵m個結(jié)點的無根樹，你可以選擇一個度數(shù)大于1的結(jié)點作為根，然后給一些結(jié)點（根、內(nèi)部結(jié)點和葉子均可）著以黑色或白色。你的著色方案應(yīng)該保證根結(jié)點到每個葉子的簡單路徑上都至少包含一個有色結(jié)點（哪怕是這個葉子本身）。
　　對于每個葉結(jié)點u，定義c[u]為從u到根結(jié)點的簡單路徑上第一個有色結(jié)點的顏色。給出每個c[u]的值，設(shè)計著色方案，使得著色結(jié)點的個數(shù)盡量少。

Input
　　第一行包含兩個正整數(shù)m, n，其中n是葉子的個數(shù)，m是結(jié)點總數(shù)。結(jié)點編號為1，2，…，m，其中編號1，2，… ，n是葉子。以下n行每行一個0或1的整數(shù)（0表示黑色，1表示白色），依次為c[1]，c[2]，…，c[n]。以下m-1行每行兩個整數(shù)a，b（1<=a < b <= m），表示結(jié)點a和b 有邊相連。

Output
　　僅一個數(shù)，即著色結(jié)點數(shù)的最小值。

Sample Input
5 3
0
1
0
1 4
2 5
4 5
3 5

Sample Output
2

Data Constraint

Hint
【數(shù)據(jù)范圍】　　
　　1<=N,M<=100000
.
.
.
.
.
.

分析

選擇任意一個點為根，答案都是相同的。
假如原來以x為根，y與x相鄰，那么x與y的顏色不可能相同。既然顏色不同，那么將根從x變成y對答案顯然也不會產(chǎn)生影響。
所以隨便選一個點為根，然后樹形DP。用f[x][0/1]表示x的子樹中，最后一個點想要得到一個白色/黑色的祖先的最小代價。
.
.
.
.
.

程序：

#include<cstdio> #include<iostream> #include<cstring> #include<cmath> using namespace std; int to[100000],cnt,from[100000],head[100000],f[100000][2],n,m,inf=2147483647,c[100000]; void insert(int x,int y) { to[++cnt]=y; from[cnt]=head[x]; head[x]=cnt; } void dp(int root,int fa) { f[root][0]=f[root][1]=1; if (root<=m) if (c[root]) f[root][0]=inf; else f[root][1]=inf; for (int i=head[root];i;i=from[i]) { if (to[i]!=fa) { dp(to[i], root); f[root][0]+=min(f[to[i]][0]-1,f[to[i]][1]); f[root][1]+=min(f[to[i]][1]-1,f[to[i]][0]); } } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%d",&c[i]); for (int i=1;i<=n-1;i++) { int x,y; scanf("%d%d",&x,&y); insert(x,y); insert(y,x); } dp(m+1,-1); printf("%d",min(f[m+1][1],f[m+1][0])); return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499938.html

總結(jié)

以上是生活随笔為你收集整理的【CQOI2009】叶子的颜色的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。