评测数据：
#1 Accepted 1ms 216.0 KiB
#2 Accepted 1ms 220.0 KiB
#3 Accepted 1ms 224.0 KiB
#4 Accepted 1ms 220.0 KiB
#5 Accepted 1ms 224.0 KiB
#6 Accepted 1ms 348.0 KiB
#7 Accepted 3ms 352.0 KiB
#8 Accepted 6ms 488.0 KiB
#9 Accepted 8ms 648.0 KiB
#10 Accepted 7ms 596.0 KiB
共计：30ms 5536KiB

#include<iostream>
using namespace std;
int n,m,head[10005],nest[20005],to[20005],f[10005][3],v[10005];
void dfs(int x,int fu){
    if(x<=n){
        f[x][v[x]]=1;
        return ;
    }
    int b[3]={0,0,0},a[3]={0,0,0};
    for(int i=head[x];i;i=nest[i]){
        int zhi=to[i];
        if(zhi==fu) continue;
        dfs(zhi,x);//找完孩子，得到孩子类型和子树染色数 
        a[v[zhi]]++;//统计各种类型的数量 
        b[v[zhi]]+=f[zhi][v[zhi]];//统计各种类型的子树需要染色的数量 
    }
    if(a[1]>a[0]){
        f[x][1]=b[0]+b[2]+b[1]-a[2]-a[1]+1;
        v[x]=1;
        return ;
    }
    else if(a[1]==a[0]){
        f[x][2]=b[1]+b[0]+b[2]+1-a[1]-a[2];
        v[x]=2;
        return;
    }
    else{
        f[x][0]=b[1]+b[0]+b[2]-a[2]-a[0]+1;
        v[x]=0;
        return;
    }
}
int main(){
    int k,x,y,biao=0;
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>k;
        v[i]=k;
    }
    for(int i=1;i<m;i++){
        cin>>x>>y;
        nest[++biao]=head[x];
        head[x]=biao;
        to[biao]=y;
        nest[++biao]=head[y];
        head[y]=biao;
        to[biao]=x;
    }
    dfs(n+1,0);
    cout<<f[n+1][v[n+1]];
    return 0;
}

#include<iostream>
using namespace std;
int n,m,head[10005],nest[20005],to[20005],f[10005][3],v[10005];
void dfs(int x,int fu){
if(x<=n){
f[x][v[x]]=1;
return ;
}
int b[3]={0,0,0},a[3]={0,0,0};
for(int i=head[x];i;i=nest[i]){
int zhi=to[i];
if(zhi==fu) continue;
dfs(zhi,x);//找完孩子，得到孩子类型和子树染色数
a[v[zhi]]++;//统计各种类型的数量
b[v[zhi]]+=f[zhi][v[zhi]];//统计各种类型的子树需要染色的数量
}
if(a[1]>a[0]){
f[x][1]=b[0]+b[2]+b[1]-a[2]-a[1]+1;
v[x]=1;
return ;
}
else if(a[1]==a[0]){
f[x][2]=b[1]+b[0]+b[2]+1-a[1]-a[2];
v[x]=2;
return;
}
else{
f[x][0]=b[1]+b[0]+b[2]-a[2]-a[0]+1;
v[x]=0;
return;
}
}
int main()
{
int k,x,y,biao=0;
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>k;
v[i]=k;
}
for(int i=1;i<m;i++){
cin>>x>>y;
nest[++biao]=head[x]; head[x]=biao; to[biao]=y;
nest[++biao]=head[y]; head[y]=biao; to[biao]=x;
}
dfs(n+1,0);
cout<<f[n+1][v[n+1]];
return 0;
}

Accepted 有效得分：100 有效耗时：0ms
cena不准啊！！！

Accepted 有效得分：100 有效耗时：0ms

经过程序证明，c是也接点u到根的简单路上最早的一个有色接点的颜色，而不是最后一个

k:=none;

if col=0 then

k:=min(dfs(son[i],0),dfs(son[i],1)+1)

else

k:=min(dfs(son[i],0)+1,dfs(son[i],1));

inc(f,k);

最后状态时min(f[n+1,0],f[n+1,1])+1

谁为根不重要，随便取的话我取n+1

thank you！

水题

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

第23 挺好的

f 表示以i为根 离i最近的i的祖先的颜色是p

（根就直接找n+1好了）

答案是 f[n+1,0] f[n+1,1] 中比较小的 加1

谁有过了的程序，粘上让小弟看看

题目描述有问题

应该改为从u到根的路径中距离u最近的

一遍AC

这题这么水，为什么过的人这么少?

很傻的treedp

从根开始，如果子树颜色统一直接染根，否则递归儿子

那么样例应该是3吧...

而且如何证明根的选择对结果没有影响呢?

不知道为什么数据范围是10000，明明是O(n)，建树有点烦……

样例谁能解释一下啊

从根开始，如果子树颜色统一直接染根，否则递归儿子

果然是水题。

2S的时限好像没有必要，树形DP可以做到O（N),

2S好像是为了O(N^2)的树形DP吧。

orz voyagec2. VJ gly，tai nb le.

膜拜voyagec2大牛，居然说这题水！

树形DP，倒着做更好写

重庆省选太水了.