题解

18 条题解

  • 2
    @ 2019-08-14 17:19:18

    评测数据:
    #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;
    }
    
  • 1
    @ 2017-08-20 21:18:46

    #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;
    }

  • 1
    @ 2017-01-07 12:41:46

    Accepted 有效得分:100 有效耗时:0ms
    cena不准啊!!!

    • @ 2017-01-07 12:42:36

      这时间**我也是醉了** !!!

    • @ 2019-08-14 17:25:13

      评测姬怎么了?爆0ms

  • 1
    @ 2009-10-08 15:53:54

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

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

  • 0
    @ 2009-09-21 17:59:18

    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!

  • 0
    @ 2009-09-18 20:25:28

    水题

  • 0
    @ 2009-09-06 17:33:13

    编译通过...

    ├ 测试数据 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

  • 0
    @ 2009-07-22 21:07:53

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

  • 0
    @ 2009-07-22 17:43:52

    题目描述有问题

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

  • 0
    @ 2009-06-30 14:26:08

    一遍AC

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

    很傻的treedp

  • 0
    @ 2009-06-23 08:09:35

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

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

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

  • 0
    @ 2009-06-13 17:22:10

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

  • 0
    @ 2009-06-11 16:35:00

    样例谁能解释一下啊

  • 0
    @ 2009-06-10 21:13:16

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

  • 0
    @ 2009-06-09 12:54:33

    果然是水题。

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

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

  • 0
    @ 2009-06-06 18:16:56

    orz voyagec2. VJ gly,tai nb le.

  • 0
    @ 2009-06-06 10:16:01

    膜拜voyagec2大牛,居然说这题水!

    树形DP,倒着做更好写

  • 0
    @ 2009-06-06 07:19:33

    重庆省选太水了.

  • 1

信息

ID
1550
难度
4
分类
概率论 | 随机化动态规划 | 树形DP 点击显示
标签
递交数
233
已通过
96
通过率
41%
被复制
1
上传者