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

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

1

1 4

2 5

4 5

3 5

Sample

2

HINT

M<=10000

N<=4996

不知道為什麼有這麼一個結論，任何一個合法節點做根答案都不變（）

然後樹dp之

每個節點都有三個狀态，這棵子樹的葉子全部滿足，這棵子樹的葉子隻剩下0沒有滿足，這棵子樹的葉子隻剩下1沒有滿足

然後yy一下就可以想出來轉移方程了

葉子全部滿足就是

1.什麼都不做，下面都滿足了

2.隻有0或者隻有1沒有滿足，把這個節點染成0或1

隻剩下0沒有滿足就是子樹全部滿足或者隻剩下0沒有滿足

隻剩下1沒有滿足就是子樹全部滿足或者隻剩下1沒有滿足

View Code