POJ PKU 2378 Tree Cutting 解题报告

又来发解题报告了

这回是树状DP

/*
 * 树状DP
 * 首先把数据想象成树状的
 * 由于输入数据为树状,不需要构建树
 * 可令degree[i]为包括i且以i为根节点的所有子节点数量
 * dp[i]为删除i后的最大子节点数量或父亲节点数量 (这里我理解了很久)
 */
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>chirld[10002];
int dp[10002] = {0}
    ,degree[10002] = {0}
    ,isJudged[10002] = {0};

int search(int pos,int &n);
int main()
{
    int n,i,a,b;
    bool isnone = true;
    scanf("%d",&n);
    for(i = 1 ; i < n ; i ++)
    {
        scanf("%d %d",&a,&b);
        chirld[a].push_back(b);
        chirld[b].push_back(a);
    }

    search(1 , n);

    for(i = 1 ; i <= n ; i ++)
        if(dp[i] * 2 <= n)
            printf("%d\n",i) , isnone = false;

    if(isnone)
        printf("NONE\n");
    return 0;
}

int search(int pos,int &n)
{
    int i,j;
    degree[pos] = 1;
    isJudged[pos] = 1;
    dp[pos] = 0;

    for(i = 0 ; i < chirld[pos].size() ; i ++)
    {
        if(!isJudged[chirld[pos].at(i)])//如果已经判断过就是父亲节点了
        {
            degree[pos] += search(chirld[pos].at(i) , n);
            if(dp[pos] < degree[chirld[pos].at(i)])
                dp[pos] = degree[chirld[pos].at(i)];
        }
    }

    if(dp[pos] < n - degree[pos])//判断父亲节点数量
        dp[pos] = n - degree[pos];
    return degree[pos];
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一名叫大蕉的程序员

简约的JAVA版本MapReduce和日常No.25

昨天做了一个小调查,说看看想看些啥。大概的分布是这样的,一个1代表一个投票。看来还是2、3比较多。 11111 希望看到"算法"回复1。 111...

20650
来自专栏开发与安全

从零开始学C++之STL(十一):容器适配器(stack、 queue 、priority_queue)源码浅析与使用示例

一、容器适配器 stack queue priority_queue stack、queue、priority_queue 都不支持任一种迭代器,它们都是...

20800
来自专栏菩提树下的杨过

中文分词组件:thulac及jieba试用手记

THULAC由《清华大学自然语言处理与社会人文计算实验室》研制推出的一套中文词法分析工具包。 官网地址:http://thulac.thunlp.org,该项目...

8320
来自专栏java达人

疫苗:Java HashMap的死循环

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condi...

268100
来自专栏tkokof 的技术,小趣及杂念

iTween那些事儿(二)

  上次我们简单浏览了一番iTween的使用和原理,这次我们换个角度,转而看看iTween目前存在的一些缺陷以及一点点可能的改进之处,当然,这些所谓的缺陷或者改...

8010
来自专栏腾讯IVWEB团队的专栏

响应式编程中 Stream 对象的实现原理

这篇文章介绍一种编程泛型,叫做响应式编程。将响应式称作“编程泛型”可能有些夸大其作用范畴,不过通过引入响应式确实会改变我们对特定问题的思考方法,就像刚接触red...

57900
来自专栏公有云大数据平台弹性 MapReduce

分布式sql引擎原理分析-逻辑执行计划生成

本文档以当前流行的分布式大数据查询引擎Presto为切入点,分析一个query语句怎么生成为一个分段的逻辑计划。

1.3K130
来自专栏栗霖积跬步之旅

一天一个设计模式:策略模式

策略模式属于对象的行为模式,其用意是针对一组算法,将每一个算法封装到具有共同接口的独立的类中,从而使得它们可以相互替换。策略模式使得算法可以在不影响客户端的情...

11420
来自专栏腾讯技术工程官方号的专栏

最强大脑,计算机中1+1=2的实现逻辑

在计算机硬件层面上,你知道1+1是如何实现的吗?本文先介绍了继电器的基本原理,然后从分析与或非等逻辑门电路入手,推导出异或门的实现,借助异或门从而实现1+1,并...

1.3K60
来自专栏后端技术探索

php进阶

基本数据类型和数组都为真复制,即为真副本,当属性为对象时,为假复制,改变副本仍会影响原对象.解决方案:

17910

扫码关注云+社区

领取腾讯云代金券