首页 > 代码库 > 1304: [CQOI2009]叶子的染色 - BZOJ

1304: [CQOI2009]叶子的染色 - BZOJ

2024-07-02 03:09:56   222人阅读

Description
给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。 对于每个叶结点u，定义c[u]为从u到根结点的简单路径上最后一个（应该是最深的那个吧）有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。
Input
第一行包含两个正整数m, n，其中n是叶子的个数，m是结点总数。结点编号为1，2，…，m，其中编号1，2，… ，n是叶子。以下n行每行一个0或1的整数（0表示黑色，1表示白色），依次为c[1]，c[2]，…，c[n]。以下m-1行每行两个整数a，b（1<=a < b <= m），表示结点a和b 有边相连。
Output
仅一个数，即着色结点数的最小值。
Sample Input
5 3
0
1
0
1 4
2 5
4 5
3 5
Sample Output
2
HINT

M<=10000
N<=4996

 

不知道为什么有这么一个结论，任何一个合法节点做根答案都不变（）

然后树dp之

每个节点都有三个状态，这棵子树的叶子全部满足，这棵子树的叶子只剩下0没有满足，这棵子树的叶子只剩下1没有满足

然后yy一下就可以想出来转移方程了

叶子全部满足就是

1.什么都不做，下面都满足了

2.只有0或者只有1没有满足，把这个节点染成0或1

只剩下0没有满足就是子树全部满足或者只剩下0没有满足

只剩下1没有满足就是子树全部满足或者只剩下1没有满足

 1 const
 2     maxn=10010;
 3 var
 4     first,c:array[0..maxn]of longint;
 5     next,last:array[0..maxn*2]of longint;
 6     f:array[0..maxn,0..2]of longint;
 7     flag:array[0..maxn]of boolean;
 8     n,m,tot:longint;
 9 
10 procedure insert(x,y:longint);
11 begin
12     inc(tot);
13     last[tot]:=y;
14     next[tot]:=first[x];
15     first[x]:=tot;
16 end;
17 
18 function min(x,y:longint):longint;
19 begin
20     if x<y then exit(x);
21     exit(y);
22 end;
23 
24 procedure dfs(x:longint);
25 var
26     i,s0,s1,s2:longint;
27 begin
28     flag[x]:=true;
29     if x<=n then
30     begin
31       f[x,0]:=1;
32       f[x,c[x]+1]:=0;
33       f[x,2-c[x]]:=1;
34       exit;
35     end;
36     i:=first[x];
37     s0:=0;
38     s1:=0;
39     s2:=0;
40     while i<>0 do
41       begin
42         if flag[last[i]]=false then
43         begin
44           dfs(last[i]);
45           inc(s0,f[last[i],0]);
46           inc(s1,min(f[last[i],1],f[last[i],0]));
47           inc(s2,min(f[last[i],2],f[last[i],0]));
48         end;
49         i:=next[i];
50       end;
51     f[x,0]:=min(s0,min(s1+1,s2+1));
52     f[x,1]:=s1;
53     f[x,2]:=s2;
54 end;
55 
56 procedure main;
57 var
58     i,x,y:longint;
59 begin
60     read(m,n);
61     for i:=1 to n do
62       read(c[i]);
63     for i:=1 to m-1 do
64       begin
65         read(x,y);
66         insert(x,y);
67         insert(y,x);
68       end;
69     dfs(m);
70     writeln(f[m][0]);
71 end;
72 
73 begin
74     main;
75 end.
View Code

 


联系
我们